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 puzzles@cotpi.com.
4 comments
Credit
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.
Post a comment
Tim Ophelders solved this puzzle:
Denote by \(E(H)\) that all horses in a set \(H\) have the same color. Now consider the case of \(n = 2\) with horses \(\{a, b\}\), then the induction hypothesis must prove that \(E(\{a\})\) and \(E(\{b\})\) implies \(E(\{a, b\})\). Note that the middle set of horses is empty for \(n = 2\), such that \(E(\{\})\) holds no matter what color is attributed to the middle set of horses. The claim that the middle horses cannot change color is therefore misleading since they don't have a unique color.
Rino Raj solved this puzzle:
This apparent paradox is an old chestnut. The induction step needs horses \(2\) through \(n - 1\) to exist which is not possible for \(n = 2\).
Ed Murphy solved this puzzle:
The induction fails when going from one horse to two horses; for \(n = 2\), the set of horses \(1\) through \(n - 1\) and the set of horses \(2\) through \(n\) are disjoint sets, so the set of middle horses, \(2\) through \(n - 1\), is an empty set.
Wonderwice Margera solved this puzzle:
The argument assumes that the group of 'middle horses', i.e. those numbered from \(2\) to \(n - 1\), has at least one horse. This fails when \(n\) equals \(2\). That is why two horses (and therefore, even more than two horses) can have different colours.