All Horses are the Same Color

If you know how to prove things by induction, then here is an amazing fact:

Theorem. All horses are the same color.

Proof. We'll induct on the number of horses. Base case: 1 horse. Clearly with just 1 horse, all horses have the same color.

Now, for the inductive step: we'll show that if it is true for any group of N horses, that all have the same color, then it is true for any group of N+1 horses.

Well, given any set of N+1 horses, if you exclude the last horse, you get a set of N horses. By the inductive step these N horses all have the same color. But by excluding the first horse in the pack of N+1 horses, you can conclude that the last N horses also have the same color. Therefore all N+1 horses have the same color. QED.

Hmmn... clearly not all horses have the same color. So what's wrong with this proof by induction?

Presentation Suggestions:
This delightful puzzle is an excellent test of student understanding of proofs by induction.

The Math Behind the Fact:
Hint: what could be wrong? You showed the base case. And you showed the inductive step, right?

Well actually, the argument in the inductive step breaks down in going from n=1 to n=2, because the first 1 horse and the last 1 horse have no horses in common, and therefore may not all have the same color.

How to Cite this Page:
Su, Francis E., et al. "All Horses are the Same Color." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

Keywords:    logic Subjects:    other Level:    Advanced Fun Fact suggested by:   Arthur Benjamin Suggestions? Use this form. 4.31 current rating Click to rate this Fun Fact...     *   Awesome! I totally dig it!     *   Fun enough to tell a friend!     *   Mildly interesting     *   Not really noteworthy and see the most popular Facts! Get the Math Fun Facts iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!