Pigeonhole principle: boys and girls seating around table

combinationscombinatoricspermutationspigeonhole-principle

Show that whenever 25 girls and 25 boys are seated around a
circular table there is always a person both of whose neighbors are
boys.

I can diagramatically / intuitively see how this is true. But when I am trying to prove it I am having hard time.

For example: if we seat all boys together we obviously have a boy surrounded by other boys.
But I cannot prove it for more general case.

Best Answer

Please use contradiction. Let's assume this is not true. What it means -

i) We cannot have more than $2$ boys seating together so we have at least $13$ boys groups ($12$ in pair and $1$ alone).

ii) There are at least $2$ girls between each group of boys (If that is not the case, you will have boys as both neighbors of a girl).

But from (i), you can see that there are at least $13$ places between boys that need to be filled with $2$ girls each (so min of $26$ girls). We do not have those many girls.