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 of a cents and b cents, and (a, b) = 1 (i.e., a and b have no common factors), determine a formula in terms of a and b to identify the largest amount of postage that CANNOT be put on an envelope using only these two denominations.Hint: In the linear combination ra + sb you may want to examine r mod b and s mod a.
3. How is the solution changed if a and b have a common divisor? Say (a,b)=d where d is the largest common divisor.For 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, c) = 1? (i.e. having 1 as the lcd)