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.

Solution

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

Copyright © 1996-2018 Alexander Bogomolny

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.

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₁, a₂, ..., a₅₀ so that position a₅₀ is next to a₁. Now we split the youngsters into "odd" and "even" groups: (a₁, a₃, ..., a₄₉) and (a₂, a₄, ..., a₅₀) which we arrange around two smaller tables. Then, by our assumption, no girls are next to each other at either table. So at each table there are at most 12 girls for a total of at most 24 girls. A contradiction. Therefore our assumption was wrong and it is always possible to find someone sitting between two girls.

Reference

1. T. Andreescu, Z. Feng, 102 Combinatorial Problems, Birkhäuser, 2003, p. 2
   

   Related material Read more...
   	Pigeonhole Principle and Extensions
   	Pigeonhole in Chess Training
   	Married Couples at a Party
   	Jumping Isn't Everything
   	Zeros and Nines
   	Teams In a Tournament
   	Divisibility of a Repunit
   	Pigeonhole in Clubs

   

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

   Copyright © 1996-2018 Alexander Bogomolny