There is no horse of a different color.

Proof (by mathematical induction):
In the base case, any group made of a single horse has only 1 color.

In the inductive case, suppose any group made of n horses has only 1 color. We show then that any group made of n+1 horses has only one color. We can then apply the same reasoning repeatedly, starting with a size 1 group, to show any size group of horses has a single color.

For any group with n+1 horses, take the first 1, ..., n of them and form a group. From the above assumption, there's only 1 color in this group. Now take the last 1, ..., n of them, which again has only one color. These groups overlap, so they must be the same single color. These groups also cover the entire group of n+1 horses, so that group must have 1 color. This completes the induction.


So, any finite group of horses has a single color. There are only finitely many horses in the world. Thus there is no horse of a different color. Q.E.D.


As a corollary, yesterday I saw a brown horse, so every horse is brown. :p

I might be wrong but a single horse does not constitute a group, does it..? You'd need to take two horses as another base case at least, in which case the proof fails horribly :p

Quote:

---

Originally Posted by NickThissen

I might be wrong but a single horse does not constitute a group, does it..?

---

Yes, yes it does. In fact no horses counts as a group of horse (size of group: 0)

Quote:

---

Originally Posted by NickThissen

You'd need to take two horses as another base case at least, in which case the proof fails horribly :p

---

Oh, so close. The proof fails horribly for the inductive step with a group of 2. Consider a group of horse A and horse B.
We assert that the group of { horse A } contains a single colour (from the base step) and that the group of { horse B } contains a single colour (again, from the base step). Our argument then falls down because we then make the conclusion from that that the group { horse A, horse B } contains a single colour. This clearly doesn't follow, because the two sub groups do not overlap.

Quote:

---

Originally Posted by NickThissen

I might be wrong but a single horse does not constitute a group, does it..?

---

I was trying to use a more intuitive word than "set", but maybe I shouldn't have.

To give credit, this is Pólya's "proof" demonstrating the need for care in inductive proofs. You can read a little more on the hilariously named Wikipedia page All horses are the same color. :)

Which reminds me of the old joke:

An engineer, a physicist and a mathematician are on a train travelling through the countryside. The engineer looks out at the fields and comments "There are sheep in that field". The physicist replies "actually, there are two separate groups of black sheep in that field". The mathematician adds "actually, there are eighty-four sheep in that field, which are black on at least one side".