Using the Pigeonhole Principle, assume there are a total of 2n + 1 people that are seated around a round table. And n+1 of them have red hair and n of them have purple hair. Then show that if n ≥ 2, then there is a person between two people that has red hair.

 

For n ≥ 2, it is given that n+1 people have red hair and n people have purple hair. 

There are more people who have red hair than purple hair.

Now, the pigeonhole principle states that if n+1 (or more) objects are put into n boxes then some box contains at least two objects. I have uploaded an image for you to imagine this concept further. In the image, at least 2 pigeons have to share a pigeonhole since there are more pigeons than the pigeonhole.

Let the n+1 people who have red hair be seated in the round table such that they are seated beside a person with purple hair.

So what happens is that in the round table, there will be pairs

RP RP RP RP RP ... and so on

but since there are more people who have red hair than purple hair, by the pigeonhole principle, at some point the red hair will run out of purple hair to sit beside with so at the end RR (both red hair) will be seated next to each other.

Consider the last set of pairs that are RP RP RR, they are in a round table, so we have shown that there is a person between two people that has red hair.

Please see the attached file for the complete solution