2019 AIME II Problems/Problem 14

Problem

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.

Solution

By the Chicken McNugget theorem, the least possible value of $n$ such that $91$ cents cannot be formed satisfies $5n - 5 - n = 91$ , so $n = 24$ . For values of $n$ greater than $24$ , notice that if $91$ cents cannot be formed, then any number $1 \mod 5$ less than $91$ also cannot be formed. The proof of this is that if any number $1 \mod 5$ less than $91$ can be formed, then we could keep adding $5$ cent stamps until we reach $91$ cents. However, since $91$ cents is the greatest postage that cannot be formed, $96$ cents is the first number that is $1 \mod 5$ that can be formed, so it must be formed without any $5$ cent stamps. There are few $(n, n + 1)$ pairs, where $n \geq 24$ , that can make $96$ cents. These are cases where one of $n$ and $n + 1$ is a factor of $96$ , which are $(24, 25), (31, 32), (32, 33), (47, 48), (48, 49), (95, 96)$ , and $(96, 97)$ . The last two obviously do not work since $92$ through $94$ cents also cannot be formed, and by a little testing, only $(24, 25)$ and $(47, 48)$ satisfy the condition that $91$ cents is the greatest postage that cannot be formed, so $n = 24, 47$ . $24 + 47 = \boxed{071}$ .

2019 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 13	Followed by Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2019 AIME II Problems/Problem 14

Problem

Solution

See Also