Problem:
For positive integers a,b, and c with a<b<c, consider collections of postage stamps in denominations a,b, and c 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 1000 cents, let f(a,b,c) be the minimum number of stamps in such a collection. Find the sum of the three least values of c such that f(a,b,c)=97 for some choice of a and b.
Solution:
First note that a must be 1 . To make every positive integer number of cents up to c−1 requires at most c−1 stamps of denominations 1 and b, and the number of c-cent stamps then required to make every positive integer number of cents up to 1000 is at most
Hence the possible values of c must satisfy the inequality
(c−1)+⌊c1000​⌋≥97
implying that c2−98c+1000≥0. Thus c≤49−1401​ or c≥49+1401​, and the integer solutions are c≤11 or c≥87. Let the number of stamps of denominations 1,b, and c be na​,nb​, and nc​, respectively, and consider two cases.
Case c≤11 :
Note that 97⋅10=970<1000, so no value of c less than 11 is possible, but 11 is a possible value of c if b=7 and (na​,nb​,nc​)=(6,1,90).
Case c≥87 :
If c=87, then nc​≤11 and na​+nb​≤86, and 87 is a possible value of c only if equality holds in both cases. However, if na​+nb​=86, then the collection contains 851 -cent stamps and 186 -cent stamp. The total value of those stamps in cents is 171 , and because 1000−171<10⋅87, only 1087 -cent stamps are needed to make all of the required amounts.
If c=88, then nc​≤11 and na​+nb​≤87, so if 88 is a possible value of c, then (na​+nb​,nc​)=(86,11) or (na​+nb​,nc​)=(87,10). In fact both 88 and 89 are possible values of c if b=87 and (na​,nb​,nc​)=(86,1,10).
The sum of the three least possible values of c is therefore 11+88+89=188​.