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
1

=================

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