A proof that all horses must be of the same color:

We will proceed by induction on the number of horses.

Basis case: n=1. Obviously, every horse is the same color as itself.

Inductive case: Assume that, for any collection of n-1 horses, they are all of the same color. Let us examine a set of n horses {x1, x2, ..., xn}. Take the subset {x1, x2, ..., x(n-1)}. This is a set of horses with n-1 members, so (by the inductive hypothesis) they must all be of the same color. Now examine the subset {x2, x3, ..., xn}. This is also a set of horses with n-1 members, so all of these must be of the same color, as well. Since (for example) x2 is a member of both subsets, all of x1, x2, ..., x(n-1), xn must have the same color as x2. So we have established that, if any collection of n-1 horses are all of the same color, then any collection of n horses must also be all of the same color.

Therefore, by induction, any collection of horses must all be of the same color, which includes the collection of all horses. Therefore, all horses are the same color.

Q.E.D.