Circular table with $25$ boys and $25$ girls and someone always sitting among $2$ boys

352 Views Asked by At

I am reading the following exercise in a section about Pigeonhole 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 am confused with the solution presented which is the following:

Number the seats around the table from $1$ to $50$. Hence we have $25$ seats with odd numbers and $25$ seats with even numbers. If no more than $12$ boys occupied the odd-numbered seats then at least $13$ boys would occupy the even-numbered seats and vice-versa. Without loss of generality, assume at least $13$ boys occupy the $25$ odd-numbered seats. Then at least $2$ of those boys must be in consecutive odd-numbered seats, and the person sitting between them will have boys as both of his/her neighbors

I don't understand:

  1. how the "no more than $12$" is determined and
  2. how do we know that if at least $13$ boys occupy the $25$ odd-numbered seats then at least $2$ seat in consecutive (odd numbered) seats. Since we have $13 \lt 25$ and $25$ is the "holes" can't be the pigeonhole principle I think.
    Can someone help understand the proof?
2

There are 2 best solutions below

0
On

I think the logic that they are following is by counting a boy for every other odd seat (1,5,9 .. 49) which would give 13. Then you would have to reject the inclusion of the boy in the 49th seat because it would make the person in the 50th seat have a neighbor of two boys (1,49) thus leaving us with a maximum of 12 boys sitting in odd numbered seats. Then the logic that follows is that the maximum number that would be able to sit on even seats should also be 12, and since 12 + 12 is 24 which is less than 25, there must be someone who has two neighbors that are both boys.

8
On

Look at it this way. The boys obviously can't be seated consecutively, neither can they be seated with a single gap between them, so the best we can do to see that no one has boys on either side of her/him, with seats numbered from $1$ to $50$ clockwise, starting with boys WLOG is a pattern of two boys together alternating with two girls together:

  • $B_1 B_2\; G_3 G_4\; B_5 B_6\;...B_{45}B_{46}\; G_{47}G_{48}..$

But how can we put the last boy and girl ?
$G_{49}B_{50}B_1B_2$ is unacceptable, as is
$B_{49}G_{50}B_1$