hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Advanced level:

# 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.

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

Keywords:    logic
Subjects:    other
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
3.97
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!