4. (4) Find the flaw with the following \"proof\" that every postage of three ce

Question

4. (4) Find the flaw with the following "proof" that every postage of three cents or more can be formed using a combination of three-cent and four-cent stamps. Basis Step: We can form postage of three cents with a single three-cent stamp and we can form postage of four cents using a single four-cent stamp. Inductive Step: Assume that we can form postage of j cents for all nonnegative integers j with jSk using just three-cent and four-cent stamps. We can then form postage of k + 1 cents by replacing one three-cent stamp with a four-cent stamp or by replacing two four-cent stamps by three three-cent stamps

Explanation / Answer

5 is the only amount you can't make.it is correct if you change "three cents or more" to "six cents or more" or just add "except 5".

Above 5, every integer is of the form.

3n(which can be formed from "n" 3cent stamps)

or 3n+1(which=3(n+1)+4,which can be made with "n-1" 3cent stamps and one 4cent stamp)

or 3n+2(which=3(n+2)+4+4)

as long as n=2 or more (and the numbers are therefore>5),you're good to go.

you either have a 3cent stamp to replace, or the values are 8cent and more and, if there are no 3cent stamps, there will be at least two 4cent stamps.and

the problem is that you can't always find either one 3-cent stamp or two-4cent stamps to replace.

for example, with 4-cent postage, you can only form it with neither a 4-cent stamp, which has neither one 3-cent stamp nor two 4-cent stamps to replace for forming 5-cent postage.

so the induction chain is broken between j=4 and 5, and so is the rest of the induction proof.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.