## All horses are the same colour

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?

[SOLVED]

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

### Credit

This puzzle is taken from: