Find the flaw with the following “proof” that every postage of three cents or mo

Question

Find the flaw with the following “proof” that every postage of three cents or more can be formed using just 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 j k 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 fourcent stamps by three three-cent stamps.

Explanation / Answer

The only problem is it tries to start too low. Five is the only amount you can't make.
The problem is that we can't always find either one 3-cent stamp or two 4-cent stamps to replace.
It is correct if we change (three cents or more)to (six cents or more) or just add (except 5).
Above five, every integer is in the form of
3k (which can be formed from "k" 3n stamps)
or 3k+1 (which = 3(k-1) + 4, which can be made up with "k-1" 3n stamps and one 4n stamp)
or 3k + 2 (which = 3(k-2) + 4 + 4)
As long as k=2 or more (and the numbers are therefore > 5), you're good to go.
You either have a 3n stamp to replace, or the value is 8c and more and, if there are no 3n stamps, there will be at least two 4n stamps.

For example, with the 4-cent postage we can only form it with a 4-cent stamp, which has neither 1 (3-cent stamp) nor 2 (4-cent stamps) to replace for forming 5-cent postage. So the

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

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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