If one plays $132$ games in $77$ days, there is a span of consecutive days with exactly $21$ games

Question

This is a high school contest question. Simple answers are required

A chess player has $77$ days to prepare for a tournament. During this time he wants to have a match everyday and to have $132$ in total. Given this, show that we can find consecutive days where the total number of matches in those days is $21$.

I started with the following two observations:

• Since he wants to play at least one match in each day, he will play at least $77$ games in $77$ days.

• To reach $132$ he needs to play $55$ matches, which means at least for $22$ days he is going to make one match.

If these $22$ days (or at least $21$ of them ) are consecutive then we are done. Considering the complement of this event takes a lot of time. I managed to answer question in that way, but I am looking for a simple solution. Thanks for any help!

Answer 1

Let $a_1, a_2, a_3, \dots, a_{77}$ be the number of games played in the $nth$ day, such that $a_i \leq 132, i\in [1, 77]$. Also consider the sequence $a_1 + 21, a_2 + 21, \dots ,a_{77} + 21$, $77 \leq a_i + 21 \leq 132 + 21 = 153$.

The 154 sequences $a_1, a_2, a_3, \dots, a_{77}$ and $a_1 + 21, a_2 + 21, \dots ,a_{77} + 21$ are all less than $153$. Thus by pigeon hole principle,

$$\Big\lceil \dfrac{154}{153}\Big\rceil = 2$$

there's at least 2 $a_j$ and $a_k + 21$, such that $a_j = a_k + 21$. We know that since $a_j$ cannot equal another $a_l$, $j \neq l$ since all the values in the sequence $a_1, a_2, a_3, \dots, a_{77}$ are distinct (at least one game a day), thus one of $a_j$ have to equal $a_k + 21$, for some $j, k \in \mathbb{Z}$. That means that there exist from $k^{th}$ day to $j^{th}$ day, there's 21 consecutive games.

Answer 2

[This answer is essentially equivalent to the already given one, but phrased in slightly friendlier language!]

Setup: Consider the following $154$ numbers, where $a_n$ means “total games played through day $n$.”

First, these $77$ numbers: $a_1, a_2, \ldots, a_{77}$.

Next, these 77 numbers: $a_1+21, a_2+21, \ldots, a_{77}+21$.

Since $1 \leq a_1$ and $a_{77}+21 \leq 132 + 21 = 153$, we have a collection of $154$ positive integers that are among the positive integers $1$ through $153$.

So: There must be a repeated integer by the Pigeonhole Principle. It cannot be that an $a_n$ repeats; it cannot be that an $a_m+21$ repeats; so, it must be that there is some $a_n = a_m + 21$. But, this means that exactly $21$ games were played between days $m$ and $n$.

QED.

Answer 3

A different solution: For $1\le i \le77$, let $a_i$ be the number of games played collectively, including day $i$. We claim there exists two days $i$ and $j$ with $i>j$ with $a_i - a_j=21$.

Since there are 77 days and 21 possible residues modulo 21, there exists 4 indices $i_1, i_2, i_3, i_4$ with $a_{i_n} - a_{i_m} \equiv 0 \pmod{21}$. Furthermore, let the four indices be congruent to $k$ modulo 21.

Then, there are 6 pigeonholes: $\{k, 21+k\}, \{21+k, 42+k\}, \{42+k, 63+k\}, \{63+k, 84+k\}, \{84+k, 105+k\}, \{105+k, 126+k\}$ with the last $1\le k \le6$ in $126+k$. Since each of $a_{i_1}, a_{i_2}, a_{i_3}, a_{i_4}$ will be counted twice, we have 8 pigeons hence by the pigeonhole principle, there exists two pigeons in one of the 6 pigeonholes. However, their difference is 21 hence there exists a $a_i$ and a $a_j$ such that $a_i-a_j = 21$ and we are done.