# Puzzle: all horses have the same color

Several answers to my previous puzzle reminded me about an old result:

Theorem: All horses have the same color.

Proof: We demonstrate this by induction over N for all the sets of horses size of size N:
- N=1: The proof is true for N = 1 (any horse has the same color as itself, so the propery is valid for any set of size 1)
- (N-1) -> N: - Assuming that the property is true for any set of (N-1) horses, we need to proof that the property holds for any set of size N. Let's pick a random set of N horses and let's do the following trick. First, we take one horse out. There are (N-1) horses left which obviously have the same color, according to the induction.  Now we put back the original horse and take another one out. We get again (N-1) horses, so the initial horse that we just added back must have the same color as the rest. In conclusion all the N horses have the same color. QED.

Now, why does this old puzzle come to my mind? Exercise left to the reader 🙂

Tags

1. Jonathan says:

The proof breaks when N=2 – there is no "the rest".

2. Jeremy D says:

The reasoning is circular. If we assume that any (N-1) subset of N horses are the same color, we are assuming that all N horses are the same color. The wording of the induction just tries to obscure this by trying to present a set operation so it looks like an algebraic operation.

The reasoning is not circular, actually, given that the classes of statements that you extend by induction are disjunct.

But Jonathan is correct – everything is OK except the case N=1 => N=2 which is not covered by the proof above. So this is where the proof breaks 🙂

4. Amigo says:

So let’s do some 6th grade math here.

Induction goes like this:

if true for 1

and true for 2

and true for 3

,,,,,

then assume it is true for N.

If it is true for N+1 then it is true for any N.