Stamp Induction problem

Suppose you have an unlimited supply of 5-cent postage stamps and 7-cent postage stamps. Show that you can make any amount of postage which is 24 cents or larger using only these stamps.




This is the coin problem. You can search the site for many variations.
– Ross Millikan
2 days ago


1 Answer


First of all, you can realize : 2424 cents postage : 2×5+2×7=242\times5+2\times7=24.

Now let N≥24N\ge24 be a integer for which there exists a solution : N=n5×5+n7×7N=n_5\times5+n_7\times7. Let’s try to realize a postage of N+1N+1 cents.

There is basically two ways to add 11 cent : 3×5−2×7=1=3×7−4×53\times5-2\times7=1=3\times7-4\times5. Problem is : you have to subtract some 55 cents or 77 cents stamps.

Suppose now that n5<4n_5<4, so that we can't add three 77 cents stamps and remove four 55 cents stamps. As N≥24N\ge24 and n5≤3n_5\le3, N−n5×5≥24−3×5=9N-n_5\times5\ge 24-3\times5=9, so there is at least two 77 cents stamps, and we can use the other solution : remove two 77 cents stamps and add three 55 cents stamps. In all cases, we can find a solution for the N+1N+1 postage problem.      Seems like you forgot to finish a sentence. I guess you could finish it with... so there is at least 9/7 7c stamps (at least 2 of them). – Myridium 2 days ago      Sorry, a misplaced "<" instead of a "w" 🙂 – Nicolas FRANCOIS 2 days ago