2
$\begingroup$

Imagine that your country's postal system only issues 2 cent and 5 cent stamps. Prove that it possible to pay for postage using only these stamps for any amount n cents, where n is at least 4.


My attempt (using Strong induction, I know we can use induction but since they say you can can apply strong induction for generalized/weak induction cases):

Base case: $$n=4: 2 \times2cents$$ $$n=5: 0 \times 5cents$$ $$n=6: 3 \times 2cents$$ $$n=7: 1 \times 2 cents + 1 \times 5 cents$$

You might ask why I have so many base cases, this is my reason why: The question states that we can pay for postage using 2 and 5 cents only. Hence, we have 3 general cases:

1: ONLY 2-cents stamps are used

2: ONLY 5-cents stamps are used

3: 2-cents and 5-cents stamps are used.

(Till now, are my base cases valid?)

Assume that for n=k, P(k) is true and that we need to show P(k+1)

$\textbf{Induction hypothesis:}$ P(k) is true when $4\le i \le k$ and $k \ge 7$

Since $4\le (k-3) \le k$ , P(k-3) or i is true by Induction hypothesis.

Now, k-3 cents can be formed using 2 and 5-cent stamps.

To get k+1 stamps, we can just replace it with $\textbf{four}$ 2-cent stamps?


Thank you! Is my proof valid or no? Any alternatives for this question using strong induction? Also, if I have used strong mathematical induction wrong or any of the steps are incorrect, please explain why.

$\endgroup$
2
$\begingroup$

Here's another induction-free proof, using the fact that integers are even or odd:

If $n$ is even, then $n=2k$ and we are done ($k$ two-cent stamps).

If $n$ is odd, so $n=2k+1$, then since $n\ge4$ we have $k\ge\frac32$ whence $k\ge2$ because $k$ is an integer. Therefore $m=k-2\ge0$, and $n=2m+5$, so we can use $m$ two-cent stamps and one five-cent stamp.

$\endgroup$
  • $\begingroup$ How did you get k ≥ 2? What's the rationale behind it @MarioCarneiro $\endgroup$ – misheekoh Dec 7 '15 at 22:01
  • $\begingroup$ Nevermind, I got it. $\endgroup$ – misheekoh Dec 7 '15 at 22:09
1
$\begingroup$

You can avoid explicit induction by verifying a finite number of cases like 4,5,6,7,8 and then note that any higher natural number is separated from one of these by a multiple of 5.

Strictly logically that last step requires induction as well but the proof is much easier.

$\endgroup$
  • $\begingroup$ Or just check the cases 4 and 5 and go from there by multiples of 2. $\endgroup$ – Barry Cipra Dec 7 '15 at 21:04
  • $\begingroup$ @Justpassingby what exactly do you mean by explicit induction. Also, do you mean that any higher natural number can be expressed as a multiple of 2 and 5? Meaning that I could get an equation to express that I can get any n-cent stamps with a formula. $\endgroup$ – misheekoh Dec 7 '15 at 21:04
1
$\begingroup$

You can do all even amounts, and you can do all odd amounts $\geq5$. It follows that the only positive amounts you cannot do are $1$ and $3$.

$\endgroup$
1
$\begingroup$

Let's assume you know how to pay $n$ cents using only 2- and 5-cents stamps. You want to find a way to pay $n+1$ cents. There are two cases:

  • If your sequence for the $n$ contains a 5-cents stamp, take it out and replace it by three 2-cent stamps.
  • If your sequence contains only 2-cents stamps, then it must contain at least two of them (remember condition $n\ge 4$?) - in this case take these two stamps out and replace them by one 5-cent stamp.

That'll be a strong induction.

$\endgroup$

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.