2019 AIME II Problems/Problem 14
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.
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 . .
Notice that once we hit all residues , we'd be able to get any number greater (since we can continually add to each residue). Furthermore, since otherwise is obtainable (by repeatedly adding to either or ) Since the given numbers are , , and , we consider two cases: when and when is not that.
When , we can only hit all residues once we get to (since and only contribute more residue ). Looking at multiples of greater than with , we get . It's easy to check that this works. Furthermore, any greater than this does not work since isn't the largest unobtainable value (can be verified using Chicken McNugget Theorem).
Now, if , then we'd need to go up to until we can hit all residues since and create distinct residues . Checking for such gives and . It's easy to check that works, but does not (since is unobtainable). Furthermore, any greater than this does not work since isn't the largest unobtainable value in those cases (can be verified using Chicken McNugget Theorem). (Also note that in the case, the residue has will not be produced until while the case has already been produced, so the highest possible value that cannot be produced would not be a number equivalent to )
Since we've checked all residues , we can be sure that these are all the possible values of . Hence, the answer is . - ktong
Obviously . We see that the problem's condition is equivalent to: 96 is the smallest number that can be formed which is 1 mod 5, and 92, 93, 94 can be formed (95 can always be formed). Now divide this up into cases. If , then 91 can be formed by using and some 5's, so there are no solutions for this case. If , then 91 can be formed by using and some 5's, so there are no solutions for this case either.
For , is the smallest value that can be formed which is 1 mod 5, so and . We see that , , and , so does work. If , then the smallest value that can be formed which is 1 mod 5 is , so and . We see that and , but 92 cannot be formed, so there are no solutions for this case. If , then we can just ignore since it is a multiple of 5, meaning that the Chicken McNuggest theorem is a both necessary and sufficient condition, and it states that meaning and . Hence, the only two that work are and , so our answer is . -Stormersyle
|2019 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|