Mathematical Induction - Postage Stamp Problem

1.1k Views Asked by At

"Find the smallest value of a such that for every integer ≥ a, it is possible to produce n cents of postage using 4 cent and 7 cent stamps."

My only guess of how to start this is to set a = 11 cents because it is the smallest value obtained with both coins.

Am I on the right track? Where do I go from here? Frankly, I'm not sure I even entirely understand what the problem is asking.

1

There are 1 best solutions below

0
On

One way to solve this problem is to write the positive integers into seven columns.

$$\begin{array}{cccc} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array}$$

We will mark values that can be made using 4-cent and 7-cent stamps by circling the number.

First, we can circle the multiples of $7$ (you can obtain such values using only 7-cent stamps). This eliminates the last column.

Next, we can circle each multiple of $4$ since these values can be obtained using only 4-cent stamps. However, once you circle a multiple of $4$, you can actually circle all the numbers below it in the same column, since those numbers are obtained by adding a multiple of 7 to the current value (add 7-cent stamps).

Thus, you just need to circle multiples of $4$ until you hit every column, from which you can then find $a$ by adding one to the largest uncircled number.

This is a nice way to visualize things (esp. when working with students), but it takes a bit more effort to prove the general result $a= mn-m-n+1$.