What Is the Smallest Value of k for Postage Using Only 4-Cent and 9-Cent Stamps?

[andytran]

Hi,

This is one of the question from my hw, i don't even understand what it's asking? Please shed some light on it.. thx


what is the smallest value of k such that any integer postage greater than k cents can be formed by using only 4-cent and 9-cent stamps? Show that k cents in postage cannot be formed and use induction to prove that all larger values can be formed.



thank you!
A.T

 

[HallsofIvy]

Obviously, since you have only 4 and 9 cent stamps, you can't "form"
1, 2, or 3 cents in postage. You could get 4 cents obviously, but not 5 cents, 6 cents, or 7 cents. You can get 8 cents and 9 cents, but not 10 cents or 11 cents. You can make 12 cents (3 four cent stamps) or 13 cents (one 9 cent stamp and one 4 cent stamp).
The question is asking you to show that, for some number k, ALL number from k+ 1 up CAN be made by combinations of 4 and 9: 4n+ 9m for some integers n and m.