An unlimited supply of 8-cent and 15-cent stamps is available. Some amounts of postage cannot be made up exactly, e.g., 7 cents, 29 cents. What is the largest unattainable amount, i.e., the amount, say , of postage which is unattainable while all amounts larger than are attainable? (Justify your answer.)
Solution
1. Identify the problem type: The problem is about finding the largest unattainable amount using two given denominations of stamps. This is a classic problem that can be solved using the Chicken McNugget Theorem (also known as the Frobenius Coin Problem).
2. State the Chicken McNugget Theorem: The theorem states that for two coprime integers and , the largest integer that cannot be expressed as a non-negative integer combination of and is given by:
Here, and .
3. Verify that the numbers are coprime: We need to check that 8 and 15 are coprime, i.e., their greatest common divisor (gcd) is 1.
Since 8 and 15 are coprime, we can apply the Chicken McNugget Theorem.
4. Apply the theorem: Using the theorem, we calculate the largest unattainable amount:
5. Conclusion: The largest unattainable amount of postage using 8-cent and 15-cent stamps is 97 cents.
The final answer is