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.
-
1$\begingroup$ This is the coin problem. You can search the site for many variations. $\endgroup$ – 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.
-
$\begingroup$ 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). $\endgroup$ – Myridium Oct 21 '16 at 15:58
-
$\begingroup$ Sorry, a misplaced "<" instead of a "w" :-) $\endgroup$ – Nicolas FRANCOIS Oct 21 '16 at 16:46