Pigeonhole in Chess Training
|
A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, in order not to tire himself, he decides not to play more than 12 games during any calendar week. Show that there exists a succession of consecutive days during which the chess master will have played exactly 21 games.
|
Solution
Copyright © 1996-2009 Alexander Bogomolny
Solution
Let a1 be the number of games played on the first day, a2 the total number of games played on the first and second days, a3 the total number games played on the first, second, and third days, and so on. Since at least one game is played each day, the sequence of numbers a1, a2, ..., a77 is strictly increasing, that is, a1 < a2 < ... < a77. Moreover, a1 ≥ 1; and since at most 12 games are played during any one week, a77 ≤ 12 × 11 = 132. Thus
| |
1 ≤ a1 < a2 < ... < a77 ≤ 132:
|
Note that the sequence a1 + 21, a2 + 21, ..., a77 + 21 is also strictly increasing, and
| |
22 ≤ a1 + 21 < a2 + 21 < ... < a77 + 21 ≤ 132 + 21 = 153.
|
Now consider the 154 numbers
| |
a1, a2, ..., a77, a1 + 21, a2 + 21, ..., a77 + 21.
|
each of them is between 1 and 153. It follows that two of them must be equal. Since a1, a2, ..., a77 are distinct and a1 + 21, a2 + 21, ..., a77 + 21 are also distinct, then the two equal numbers must be of the forms ai and aj + 21. Since the number games played up to the ith day is ai = aj + 21, we conclude that on the days j + 1, j + 2, ..., i the chess master played a total of 21 games.
Reference
- Beifang Chen, The Pigeonhole Principle
Copyright © 1996-2008 Alexander Bogomolny
|
