Pigeonhole principle: boys and girls seating around table

Question

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.

Answer 1

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.

Answer 2

Here's how you can do it with PP, given your tag.

Label the seats $s_1, \ldots s_{50}$.
Let the holes be the sets of seats $s_1, s_3, \ldots s_{49}$, and $s_2, s_4, \ldots s_{50}$, and let the pigeons be the boys.
By PP, one of these sets (WLOG the even set) has at least $ \lceil \frac{25}{2} \rceil = 13 $ boys.

Now, let the holes be the sets of seats $s_2, s_4$ and $s_6, s_8$ and $\ldots $ and $s_{42}, s_{44}$ and $s_{46}, s_{48}, s_{50}$. There are 12 holes. Let the pigeons be the boys.
By PP, one of these sets has at least $ \lceil \frac{13}{12} \rceil = 2 $ boys.
If it's a set with exactly 2 seats, then these boys are next to each other.
If it's the set with 3 seats, then these boys are also next to each other.