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 🙂

Comments (5)

  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.

  3. AdiOltean says:

    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.

    In your case, your’re assuming…and

    you know what assume is? Making an "ass" of "u" and "me".