3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess that in the first sentence you should write "It is given that for all $n\geq 0$" $\endgroup$ – ZFR Dec 21 '17 at 20:13
  • $\begingroup$ Very elegant solution! +1. But let me ask you one question: How did you derive that $l-m\leq 19$? $\endgroup$ – ZFR Dec 21 '17 at 20:16
  • 1
    $\begingroup$ @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 $\endgroup$ – Mastrem Dec 21 '17 at 20:26
  • $\begingroup$ Thanks a lot! Please correct the first sentence as I said above. $\endgroup$ – ZFR Dec 21 '17 at 20:27
  • $\begingroup$ @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\}$ $\endgroup$ – Mastrem Dec 21 '17 at 20:29
1
$\begingroup$

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$.

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