Maths Olympiad Prep

Library / /273 of 520

Number theory Difficulty 6.9 National olympiad Find the answer

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 nn, of postage which is unattainable while all amounts larger than nn are attainable? (Justify your answer.)

A number or a short expression. Spacing and $ signs are ignored.

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 aa and bb, the largest integer that cannot be expressed as a non-negative integer combination of aa and bb is given by:
n=abab n = ab - a - b
Here, a=8a = 8 and b=15b = 15.

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.
gcd(8,15)=1 \gcd(8, 15) = 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:
n=815815 n = 8 \cdot 15 - 8 - 15
n=120815 n = 120 - 8 - 15
n=12023 n = 120 - 23
n=97 n = 97

5. Conclusion: The largest unattainable amount of postage using 8-cent and 15-cent stamps is 97 cents.

The final answer is 97\boxed{97}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.