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 🙂