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. <https://www.math.hmc.edu/funfacts>.
Fun Fact suggested by: