Prove that any integer amount of postage from 18 cents and up can be made using only 4-cent and 7-cent stamp. Assume an infinite supply of stamps

Question

My question reads as follows:

Prove that any integer amount of postage from 18 cents and up can be made using only 4-cent and 7-cent stamp. Assume an infinite supply of stamps. Use induction

Firstly, I must construct an equation to allow me to evaluate this problem with induction. The equation I have decided on is $N=4m+7n$ and $N>17$ so the base case must be in this case that N = 18.

Evaluating the base case I achieve that 18 is in fact equal to 18. Great, now I can move onto the induction step.

However, I am unsure as to how to continue this problem. And am in need of assistance. Thanks

Answer 1

Hint:

Think of this as four separate induction problems, whose base cases are 18 cents, 19 cents, 20 cents, and 21 cents, respectively.

Answer 2

You can get $18 = 2 \cdot 7 + 1\cdot 4$, $19 = 1 \cdot 7 + 3 \cdot 4$, $20 = 0 \cdot 7 + 5 \cdot 4$, $21 = 3 \cdot 7 + 0 \cdot 4$. From those you get all larger numbers by adding $4$. You need to also show that 17 is impossible (try all posibilities, there aren't that many...).

This is called Frobenius problem, for 2 values of stamps (like here) the largest value that can't be represented is $a_1 a_2 - a_1 - a_2$, here $4 \cdot 7 - 4 - 7 = 17$.

Answer 3

There are four standard answers

1) Google the Frobenuis coin problem.

2) Google the (shudder) "Chicken McNuggets" problem (ugh).

3) Show that $4*2+ 7*(-1) = 3*7 + 4*(-5) = 1$ so if you have $N= 4m + 7n$ then $N + 1 = 4(m+2) + 7*(n-1) = 4(m-5) + 7(n+3)$ which will work so long as either $n > 0$ or $m > 4$.

4) If you have $N = 4m + 7n$ is possible then $N+4 = 4(m+1) + 7n$ is possible. Then do ** $4$ ** base cases. $18,19,20, 21$ If those four base cases work then so do $4k$ plus any of those four base cases.

=======

More detail

3) Base Case: $18 = 4*1 + 2*7$.

Induction Step: If $N = 4*m +7*n$ and $N \ge 18$ then if $n \ge 1$ then $4*(m+2) + 7*(n-1) = 4*m + 7*n + 8-7 = N+1$.

If $n = 0$ then $N=4*m \ge 18$ so $m \ge 4.5$ so $m \ge 5$.

Then $4(m-5) + 7*(n+3) = (4m + 7n) + (-20+21) = N+1$.

........

4) Base cases:

$18= 4*1 + 7*1$

$19 = 4*3 + 7*1$

$20 = 4*5 + 7*0$

$21 = 4*0 + 7*3$.

Induction step:

If $N = 4m + 7n$ then $N + 4 = 4(m+1) + 7n$.

As as all $N$ are equivalent to $18,19,20$ or $21\pmod 4$ that covers all cases even though we need a different base case for each equivalence class.

Answer 4

Hint: what you have to show is that for each $N \ge 18$, there exist $m$ and $n$, such that $N = 4m + 7n$. This is true for $N = 18$. Now you have to assume it's true for some $N \ge 18$ and show that it is true for $N + 1$, i.e., given $m$ and $n$ such that $N = 4m + 7n$, you have to find $m'$ and $n'$ such that $N + 1 = 4m' + 7n'$, i.e., such that:

$$4m + 7n + 1 = 4m' + 7n'$$

To derive $m'$ and $n'$ from $m$ and $n$, you can use $2\cdot4 = 7 + 1$, if $n > 0$, and you can use $4 \cdot 5 + 1 = 3 \cdot 7$, if $n = 0$, (because in the latter case as $N \ge 18$, $m \ge 5$).