What is wrong with the following \"proof\" showing all horses are the same color

Question

What is wrong with the following "proof" showing all horses are the same color: Induct on the number of horses, n. If n = 1, there is clearly only one color. Suppose now any collection of n horses has one color and look at a group of n + 1 horses, {h_1,, h_n + 1}. Then the two collections {h_1,, h_n} and {h_2,, h_n + 1} both have n horses each and so the induction hypothesis shows each set of horses has only one color. Since the two sets of horses overlap, there is only one color among all the horses. Thus all horses have the same color.

Explanation / Answer

Since the (n+1)th horse may or may not have the color which the other n horses has.

So the group {h1,....,hn} and {h2,....,hn+1} can not follow the induction hypothesis

Hence the proof is not valid

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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