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 Oct 21 '16 at 15:27

First of all, you can realize : $24$ cents postage : $2\times5+2\times7=24$.

Now let $N\ge24$ be a integer for which there exists a solution : $N=n_5\times5+n_7\times7$. Let's try to realize a postage of $N+1$ cents.

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

Suppose now that $n_5<4$, so that we can't add three $7$ cents stamps and remove four $5$ cents stamps.

As $N\ge24$ and $n_5\le3$, $N-n_5\times5\ge 24-3\times5=9$, so there is at least two $7$ cents stamps, and we can use the other solution : remove two $7$ cents stamps and add three $5$ cents stamps.

In all cases, we can find a solution for the $N+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 Oct 21 '16 at 15:58
• Sorry, a misplaced "<" instead of a "w" :-) – Nicolas FRANCOIS Oct 21 '16 at 16:46