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