Problem:
For positive integers , and with , consider collections of postage stamps in denominations , and cents that contain at least one stamp of each denomination. If there exists such a collection that contains sub-collections worth every whole number of cents up to cents, let be the minimum number of stamps in such a collection. Find the sum of the three least values of such that for some choice of and .
Solution:
First note that must be 1 . To make every positive integer number of cents up to requires at most stamps of denominations 1 and , and the number of -cent stamps then required to make every positive integer number of cents up to 1000 is at most
Hence the possible values of must satisfy the inequality
implying that . Thus or , and the integer solutions are or . Let the number of stamps of denominations , and be , and , respectively, and consider two cases.
Note that , so no value of less than 11 is possible, but 11 is a possible value of if and .
If , then and , and 87 is a possible value of only if equality holds in both cases. However, if , then the collection contains 851 -cent stamps and 186 -cent stamp. The total value of those stamps in cents is 171 , and because , only 1087 -cent stamps are needed to make all of the required amounts.
If , then and , so if 88 is a possible value of , then or . In fact both 88 and 89 are possible values of if and .
The sum of the three least possible values of is therefore .
The problems on this page are the property of the MAA's American Mathematics Competitions