Solution to State the Pigeonhole Principle. A chess player wants to prepare for a championship match by … - Sikademy
Author Image

Archangel Macsika

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

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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 ai , 1 ≤ i ≤ 77 be the number of games played till ith day, including the games played on the ith day. Then,

a1 < a2 < . . . < a77 ≤ 132 (1)

a1 + 21 < a2 + 21 < . . . < a77 + 21 ≤ 132 + 21 = 153 (2)

Note that there does not exist ai , aj such that i \neq j, 1 ≤ i, j ≤ 77 and ai = aj . Similarly, in equation (2), a1 + 21 to a77 + 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., ai = aj + 21 and this implies that ai − aj = 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. 


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-747-qpid-632