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| |Store|

Copyright © 1996-2017 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 a1, a2, ..., a50 so that position a50 is next to a1. Now we split the youngsters into "odd" and "even" groups: (a1, a3, ..., a49) and (a2, a4, ..., a50) 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...

  2. Pigeonhole Principle and Extensions
  3. Pigeonhole in Chess Training
  4. Married Couples at a Party
  5. Jumping Isn't Everything
  6. Zeros and Nines
  7. Teams In a Tournament
  8. Divisibility of a Repunit
  9. Pigeonhole in Clubs
  10. |Contact| |Front page| |Contents| |Up| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

 62034033

Search by google: