# Pigeonhole principle in contest math problem

A chess player trains by playing at least one game per day, but, to avoid exhaustion, no more that $12$ games a week. Prove that there is a group of consecutive days in which he plays exactly $20$ games.

I was able only to reformulate this problem: let $\{x_n\}$ is a sequence of positive integers such that $x_{7(k-1)+1}+\dots+x_{7k}\leqslant 12$. Prove that there there is a block of consecutive terms such that its sum is equal to $20$. Unfortunately, it did not help me.

Can any give detailed solution please?

It would be interesting to take a look at the solution.

Remark: Please do not duplicate this question with others since the solution provided by user Mastrem is original and differ from other solutions.

• Possible duplicate of Chess Master Problem – Aqua Dec 21 '17 at 20:01
• – Aqua Dec 21 '17 at 20:04
• – Aqua Dec 21 '17 at 20:05

We define a sequence $a_1,a_2,\ldots$, by letting $a_i$ be the amount of games played on day $i$. It is given that for all $n\in\mathbb{N}$, we have: $$a_{7n+1}+a_{7n+2}+a_{7n+3}+a_{7n+4}+a_{7n+5}+a_{7n+6}+a_{7n+7}\le 12$$ Now, define $$b_k=\sum_{i=1}^{k}a_i$$ for all $k=1,2\ldots$. By the pigeonhole principle, we can find some $l>m$ such that: $$b_l\equiv b_m\pmod {20}$$ and $l-m\le 20$. This means that: $$\sum_{i=m+1}^{l}a_i\equiv 0\pmod {20}$$ and $$1\le\sum_{i=m+1}^{l}a_i<3\cdot 12=36$$ Since the chess player plays at least one game per day and $l>m$. We conclude that: $$\sum_{i=m+1}^{l}a_i=20$$ and we are done.

• I guess that in the first sentence you should write "It is given that for all $n\geq 0$" – ZFR Dec 21 '17 at 20:13
• Very elegant solution! +1. But let me ask you one question: How did you derive that $l-m\leq 19$? – ZFR Dec 21 '17 at 20:16
• @RFZ Sorry, it should be $20$. Take any $21$ (consecutive) values of $b_i$. Since there are only $20$ possible residues $\pmod {20}$, at least two of those are congruent $\pmod{20}$ by the pigeonhole principle – Mastrem Dec 21 '17 at 20:26
• Thanks a lot! Please correct the first sentence as I said above. – ZFR Dec 21 '17 at 20:27
• @RFZ I don't get what I did wrong there. I just use one of the two common definitions of $\mathbb{N}$, namely $\mathbb{N}=\{0,1,2,\ldots\}$ – Mastrem Dec 21 '17 at 20:29

Certainly it's possible for the period to be as long as $20$ days - playing only one game per day - so let's see if $20$ days is also sufficient to produce a $20$-game group of days.

For $0 \le i \le 20$, let $G_i$ be the total cumulative number of games played by the end of the $i^{th}$ day (with $G_0 = 0$), and consider these values modulo $20$.

Now we have $21$ terms taking $20$ possible values $\bmod 20$, so the pigeonhole principle gives us that there must be two values $i < j$ such that $G_i \equiv G_j \bmod 20$. Therefore $G_j-G_i$, the total number of games played on days $i+1$ to $j$, is a multiple of $20$.

However, the maximum number of games played in $20$ days is $3\cdot12-1=35$, so we must have $G_j-G_i=20$, so exactly $20$ games were played in the period from day $i+1$ through to day $j$.

Notice that this also works if the maximum number of games per week is $13$.