basic induction probs

Hello guys I have this problem which has been really bugging me. And it goes as follows:

Using induction, we want to prove that all human beings have the same hair colour. Let S(n) be the statement that “any group of n human beings has the same hair colour”.

Clearly S(1) is true: in any group of just one, everybody has the same hair colour.

Now assume S(k), that in any group of k everybody has the same hair colour. If we replace any one in the group with someone else, they still make a total of k and hence have the same hair colour. This works for any initial group of people, meaning that any group of k + 1 also has the same hair colour. Therefore S(k + 1) is true.

I cant seem to figure out where the problem lies in this proof. I have tried a few things and I have concluded the base case is correct. But other than that I can't seem to disprove this proof.

Solution 1:

The base case is correct.

Inductive step:

Assume that the result is true for $n = k$, which is to say that everybody in a group of $k$ people has the same hair colour.

For the proof to work, you now have to prove that $P(k)$ implies $P(k+1)$, but it doesn't. Just because it's true that for any group of $k$ people, everyone in the group has the same hair colour, it doesn't follow that for any group of $k+1$ people, everyone in the group has the same hair colour. One counterexample suffices to disprove the claim: take a group with one person in, who has red hair. Now add someone with blonde hair.

Solution 2:

The problem is when you go from 1 to 2 persons.

Assuming S(K) valid for k=1: that in any group of 1 human being, everybody has the same hair colour

Now you should be able to prove the validity of S(K+1): the equivalent to any group of 2 human beings.

Ok. Let's try. If you have any group of 2 human beings in a room, then you ask one of them to go out. The one who stayed is blond, for example. When the first person returns, then you ask to the blond one (who stayed) to go out now, and apply the hipothesis: being a group of 1 human being, "all" should have the same hair colour, ANY COLOUR, for example, brown hair.