Answer to Question #272784 in Discrete Mathematics for Utkarsh Kumar

Question

State the Pigeonhole Principle. A chess player wants to prepare for a championship match by playing

some practice games in 77 days. She wants to play at least one game a day but no more than 132

games altogether. Prove that there is a period of consecutive days within which she plays exactly 21

games

Answer 1

pigeonhole principle states that if n items are put into m containers, with n>m, then at least one container must contain more than one item.

Let a_i , 1 ≤ i ≤ 77 be the number of games played till i^th day, including the games played on the i^th day. Then,

a₁ < a₂ < . . . < a₇₇ ≤ 132 (1)

a₁ + 21 < a₂ + 21 < . . . < a₇₇ + 21 ≤ 132 + 21 = 153 (2)

Note that there does not exist a_i , a_j such that i $\neq$ j, 1 ≤ i, j ≤ 77 and a_i = a_j . Similarly, in equation (2), a₁ + 21 to a₇₇ + 21 are distinct. It follows that there exist 2 × 77 = 154 summands (pigeons), and 153 distinct integer values (pigeonholes). Therefore, there exist two summands having the same value. i.e., a_i = a_j + 21 and this implies that a_i − a_j = 21. Thus, there exist a period of i−j consecutive days during which exactly 21 games are played, i.e., days j + 1, j + 2, . . . , i.