3
$\begingroup$

A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, to avoid tiring 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.

I am not able to understand how to use pigeon hole principle here. What is the intuition for using pigeon hole principle here?

$\endgroup$
  • $\begingroup$ Hello Siddharth, Is this problem from "An Excursion in Mathematics"? $\endgroup$ – user249332 Sep 18 '15 at 13:43
  • $\begingroup$ Sorry but I don't know, it was my quiz problem. $\endgroup$ – Siddharth Sep 18 '15 at 13:45
  • 1
    $\begingroup$ Related: 1, 2. $\endgroup$ – Daniel Fischer Sep 18 '15 at 13:50
4
$\begingroup$

It's a bit tricky to see Pigeon Hole Principle. Here we note that the total game play is not to exceed $11\times 12=132$ games. Now, if we denote $s_i$ to be the total games played after the $i$-th day. Then look at the sequence of $\color{red}{154}$ numbers: $$s_1,s_2,\dots, s_{77}, s_{1}+21,\dots, s_{76}+21,s_{77}+21$$ Now these are the "pigeons" whereas their values are "holes". Clearly, the maximal value (i.e. the number of holes) is $132+21=\color{red}{153}$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Let $a_n$ be the numbers of game played until day $n$ and $A$ the set $\{a_1,a_2,\ldots,a_{77}\}$.

We have to prove that $21\in A-A$. Assuming the opposite, we have that $A$ and $A+21$ are disjoint sets, so the cardinality of $B=A\cup(A+21)$ is $2\cdot 77=154$. However, $$ \max B \leq 21+\max A \leq 21+12\cdot 11 = 153 $$ so $A$ has to intersect $A+21$ and the claim follows.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.