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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.