2019 AIME II Problems/Problem 14
Problem
Find the sum of all positive integers such that, given an unlimited supply of stamps of denominations
and
cents,
cents is the greatest postage that cannot be formed.
Solution
By the Chicken McNugget theorem, the least possible value of such that
cents cannot be formed satisfies
, so
. For values of
greater than
, notice that if
cents cannot be formed, then any number
less than
also cannot be formed. The proof of this is that if any number
less than
can be formed, then we could keep adding
cent stamps until we reach
cents. However, since
cents is the greatest postage that cannot be formed,
cents is the first number that is
that can be formed, so it must be formed without any
cent stamps. There are few
pairs, where
, that can make
cents. These are cases where one of
and
is a factor of
, which are
, and
. The last two obviously do not work since
through
cents also cannot be formed, and by a little testing, only
and
satisfy the condition that
cents is the greatest postage that cannot be formed, so
.
.
See Also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.