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.

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