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