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$
3
  • $\begingroup$ Hello Siddharth, Is this problem from "An Excursion in Mathematics"? $\endgroup$
    – user249332
    Commented Sep 18, 2015 at 13:43
  • $\begingroup$ Sorry but I don't know, it was my quiz problem. $\endgroup$
    – Siddharth
    Commented Sep 18, 2015 at 13:45
  • 1
    $\begingroup$ Related: 1, 2. $\endgroup$ Commented Sep 18, 2015 at 13:50

2 Answers 2

5
$\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}$.

$\endgroup$
3
$\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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .