All horses are the same colour; we can prove this by induction on the number of horses in a given set. Here's how: "If there's just one horse then it's the same colour as itself, so the basis is trivial. For the induction hypothesis, horses \(1\) through \(n - 1\) are the same colour, and similarly horses \(2\) through \(n\) are the same colour. But the middle horses, \(2\) through \(n - 1\), can't change colour when they're in different groups; these are horses, not chameleons. So horses \(1\) and \(n\) must be the same colour as well, by transitivity. Thus all \(n\) horses are the same colour; QED." What, if anything, is wrong with this reasoning?
Sunday, November 4, 2012
Please email your solutions to firstname.lastname@example.org.
This puzzle is taken from:
- Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Concrete Mathematics: A Foundation for Computer Science. 2nd ed. Reading, Massachusetts: Addison-Wesley, 1994. 31. Problem 1.