Browse · MATH
Printjmc
number theory senior
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 must be at least . For a value of to work, we must not only be unable to form the value , but we must also be able to form the values through , as with these five values, we can form any value greater than by using additional cent stamps. Notice that we must form the value without forming the value . If we use any cent stamps when forming , we could simply remove one to get . This means that we must obtain the value using only stamps of denominations and . Recalling that , we can easily figure out the working pairs that can used to obtain , as we can use at most stamps without going over. The potential sets are , and . The last two obviously do not work, since they are too large to form the values through , and by a little testing, only and can form the necessary values, so . .
Final answer
71