# Twenty five boys and twenty five girls

Twenty five boys and twenty five girls sit around a table. Prove that it is always possible to find a person both of whose neighbors are girls.

|Contact| |Front page| |Contents| |Up| |Store|

Copyright © 1996-2017 Alexander BogomolnyTwenty five boys and twenty five girls sit around a table. Prove that it is always possible to find a person both of whose neighbors are girls.

### Solution 1

For the sake of contradiction we assume that there is a sitting arrangement such that there is no one sitting between two girls. We call a *block* any group of same gender sandwiched between a pair of another gender. By our assumption, each girl block has at most 2 girls and there are at least 2 boys in the gap between two consecutive girl blocks. Hence there are at least [25/2]+1 = 13 girl blocks and at least 2×13 sitting in the gaps in-between the 13 girl blocks. But we only have 25 boys. A contradiction. Therefore our assumption was wrong and it is always possible to find someone sitting between two girls.

### Solution 2

We again assume that there is a sitting arrangement such that there is no one sitting between two girls. We denote the positions a_{1}, a_{2}, ..., a_{50} so that position a_{50} is next to a_{1}. Now we split the youngsters into "odd" and "even" groups: _{1}, a_{3}, ..., a_{49})_{2}, a_{4}, ..., a_{50})

### Reference

- T. Andreescu, Z. Feng,
*102 Combinatorial Problems*, Birkhäuser, 2003, p. 2|Contact| |Front page| |Contents| |Up| |Store|

Copyright © 1996-2017 Alexander Bogomolny

62034033 |