Find the sum of all positive integers $n$ such that, given an unlimited supply of stamps of denominations $5,n,$ and $n+1$ cents, $91$ cents is the greatest postage that cannot be formed.

Question

Bytelearn · Accepted Answer

Problem Description: We are dealing with a problem related to the Frobenius coin problem, which asks for the largest amount of postage that cannot be formed using given denominations. According to the problem, we have stamps of denominations $5$, $n$, and $n+1$ cents, and we know that $91$ cents is the greatest amount that cannot be formed. We need to find all such $n$ that satisfy this condition.Solution Approach: The Frobenius coin problem has a solution for two denominations, which is given by $(a-1)(b-1)-1$ where $a$ and $b$ are relatively prime (their greatest common divisor is $1$). In our case, we have three denominations, but since $5$ is a factor of $n$ and $n+1$, we can ignore it for the purpose of finding the largest unattainable postage. We need to find $n$ such that $n$ and $n+1$ are relatively prime (which they always are, since consecutive integers are always relatively prime), and their product minus $1$ is equal to $91$.Equation Setup: We set up the equation $(n)(n+1)-1 = 91$. This simplifies to $n^2 + n - 92 = 0$.Quadratic Equation: We need to solve the quadratic equation $n^2 + n - 92 = 0$. This can be factored into $(n-8)(n+12) = 0$.Solution Verification: The solutions to the equation are $n = 8$ and $n = -12$. However, since we are looking for positive integers, we discard $n = -12$.Final Result: Now we have found that $n = 8$ is a solution. Since $n$ and $n+1$ are consecutive integers, they are relatively prime, and their product minus $1$ gives us $91$. This means that with denominations of $5$, $8$, and $9$ cents, the greatest postage that cannot be formed is $91$ cents.Sum Calculation: Since the problem asks for the sum of all such $n$, and we have found only one value of $n$ that satisfies the condition, the sum is simply $n = 8$.

Find the sum of all positive integers $n$ such that, given an unlimited supply of stamps of denominations $5$ , $n$ , and $n+1$ cents, $91$ cents is the greatest postage that cannot be formed.

Full solution

More problems from GCF and LCM: word problems

Related topics

Find the sum of all positive integers nnn such that, given an unlimited supply of stamps of denominations 555, nnn, and n+1n+1n+1 cents, 919191 cents is the greatest postage that cannot be formed.

Find the sum of all positive integers $n$ such that, given an unlimited supply of stamps of denominations $5$ , $n$ , and $n+1$ cents, $91$ cents is the greatest postage that cannot be formed.