Two Stamp Problem

1. Given a supply of postage stamps of 4 cent denomination and 7 cent denomination, what is the largest amount of postage that CANNOT be put on an envelope using only these two denominations?

2. If the two denominations have values ofcents andacents, and (b,a) = 1 (i.e.,bandahave no common factors), determine a formula in terms ofbandato identify the largest amount of postage that CANNOT be put on an envelope using only these two denominations.bHint: In the linear combinationyou may want to examinera + sbmodrandbmods.a

3. How is the solution changed ifandahave a common divisor? Say (a,b)=d where d is the largest common divisor.bFor a numerical example here, try stamps with denominations of 4 cents and 6 cents.

4. Compare this to the

McNuggets problem. What is the generalization for three denominations of stamps with (,a,b) = 1? (i.e. having 1 as the lcd)c

Return to