Problem 9 Find the flaw with the following \"proof\" that everyone has the same

Question

Problem 9 Find the flaw with the following "proof" that everyone has the same colored hair Bogus proof The proof is by induction on n. Base Case: Take one person. Obviously, they have the same color hair since there is only one Inductive Step: Assume that every group of n people has the same colored hair. Take a group of n+1 people. Take the first person out of the group. Now we are left with a group of n people, so they must have the same color hair. Put that first person back in the group, and take out the last person. Again we have a group of n people, so they must have the same color hair. So, the first person has the same color hair as the middle people, as does the last person. So all n+1 people have the same color hair.

Explanation / Answer

The flaw is in the Inductive step. Where we assume that 'every' group of n people have the same hair color. We cannot assume that, we can only that first n group of people have the same color, then we should add a new person to that group. If we directly assume that every group of n people have the same hair color, this assumption itself means that all people have same hair color. So we cannot directly assume that.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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