Discrete Math

Let \(S = \set{c_1, c_2, \dots, c_n}\) represent a set of \(n\) cows, each labelled \(c_k\text{.}\) For \(n = 1\text{,}\) this is a set of 1 cow, of which all cows have the same colour, vacuously.

Then, assume the result is true for a set of \(k\) cows for some \(k \in \mathbb{N}\text{.}\) Then, we want to show that a set of \(k+1\) cows all have the same colour.

Consider a group of \(k+1\) cows. Remove any one cow, and then a group of \(k\) remains, which by the induction hypothesis all have the same colour. Then, return the cow and remove any one different cow, again leaving a group of \(k\) cows, which all have the same colour. Then, the first removed cow has the same colour as the rest of the group, and the second removed cow has the same colour as the rest of the group. Thus, the first and second removed cow have the same colour, and so all \(k+1\) cows have the same colour. Thus, by induction, all cows are the same colour.