Subjects number theory

Postage Stamps

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Postage Stamps


1. **Problem statement:** We want to find which postage amounts can be made using only five-cent and six-cent stamps. Specifically, is there a number $N$ such that for every $n \geq N$, we can make $n$ cents of postage using these stamps? 2. **Known fact:** We can make 20 cents using four five-cent stamps: $$4 \times 5 = 20.$$ This is our base case. 3. **Inductive hypothesis:** Assume for some $k \geq 20$, every amount of postage from 20 cents up to $k-1$ cents can be made using five- and six-cent stamps. 4. **Goal:** Show that postage of $k$ cents can also be made using these stamps. 5. **Proof for $k < 25$:** We check the amounts 21, 22, 23, and 24 explicitly: - 21 = $3 \times 5 + 1 \times 6$ - 22 = $2 \times 5 + 2 \times 6$ - 23 = $1 \times 5 + 3 \times 6$ - 24 = $4 \times 6$ 6. **Proof for $k \geq 25$:** Since $k - 5 \geq 20$, by the inductive hypothesis, $k - 5$ cents can be made using five- and six-cent stamps. Adding one more five-cent stamp gives $k$ cents: $$k = (k - 5) + 5.$$ 7. **Why is this not circular reasoning?** Induction works by proving a base case (here, 20 cents) and then showing that if the statement holds for all values up to $k-1$, it must hold for $k$. We do not assume the statement for $k$; we assume it only for smaller values to prove it for $k$. This step-by-step approach builds the truth for all $n \geq 20$. 8. **Conclusion:** There exists $N = 20$ such that for all $n \geq N$, postage of $n$ cents can be made using five- and six-cent stamps. **Final answer:** Yes, for all $n \geq 20$, we can make $n$ cents of postage using five- and six-cent stamps.