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

• Anonymous
  September 13, 2005
  The proof breaks when N=2 - there is no "the rest".
• Anonymous
  September 14, 2005
  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.
• Anonymous
  September 14, 2005
  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 :-)
• Anonymous
  September 28, 2005
  The comment has been removed
• Anonymous
  April 04, 2008
  PingBack from http://drinksairportsblog.info/antimail-puzzle-all-horses-have-the-same-color/