From Introductory Combinatorics by Richard Brualdi
We have a chess master. He has 11 weeks to prepare for a competition so he decides that he will practice everyday by playing at least 1 game a day. To make sure that he's able to take a couple of breaks, he also decides that he wont play more than 12 games per week.
My question is, how do you prove/dis-prove that there will be a succession of (consecutive) days in which he will play k games, $k \geq 22$?
Specifically, I don't quite understand the use of the pigeonhole principle here.
Thanks in advance! 😀
EDIT
I'll try to clarify what I'm asking:
The goal is to prove that for every possible practice schedule that the chess master makes, there will always be a consecutive sequence of days such that he plays exactly k games.
So for example, if k = 22, how do you prove that no matter what his schedule is like, he will always play exactly k games in r days, $1 \leq r\leq 77$.
My main question is: what is the general method for proving different values of k? Are there values of k (from 1 to 132 inclusive) that are impossible to obtain?
Note that he does not necessarily have to play 132 games within 77 days!
Also, keep in mind the bounds of k.
Best Answer
For $\displaystyle 1 \le k \le 24$ you can definitely show that the master must have played exactly $k$ games on some set of consecutive days, using pigeonhole principle.
Suppose the total number of games the master has played till the end of day $\displaystyle j$ is $\displaystyle g_j$.
Now consider the $\displaystyle 154$ numbers: $\displaystyle g_1, g_2, \dots, g_{77}, g_1 + k, g_2 + k, \dots, g_{77} + k$
These are a set of $\displaystyle 154$ numbers between $\displaystyle 1$ and $\displaystyle 132+k$.
For $\displaystyle k \lt 22$, two of these must be equal. Since $\displaystyle g_i \neq g_j$ (at least one game a day) we must have that $\displaystyle g_j + k = g_i$ for some $\displaystyle i,j$.
For $\displaystyle k=22$ we must have that the numbers are $\displaystyle 1,2, \dots, 154$, in which case, the first (and last) $\displaystyle 22$ days, the master must have played $\displaystyle 1$ game everyday.
For $\displaystyle k=23$, we can assume $\displaystyle g_i \neq 23$, and since $g_i \ge 1$, we have $g_i + k \neq 23$.
Thus by an argument similar to above, we must have have $\displaystyle 154$ numbers taking all values in $\displaystyle 1, 2, \dots, 155$, except $\displaystyle 23$ and the master must have played $\displaystyle 1$ game each of the last $\displaystyle 23$ days.
For $\displaystyle k=24$, you can show that the master must have played $\displaystyle 1$ game the first $\displaystyle 23$ days (after eliminating one of the numbers in $\displaystyle 133, 134 \dots$), then a big number of games the next, violating the $\displaystyle 12$ games per week restriction (this is where we actually used that restriction for a specific week).
We might be able to use this kind of argument to show for $\displaystyle k$ close to $\displaystyle 24$, but for larger $\displaystyle k$, I am guessing that you can find a set of games which will miss that (perhaps a computer search will help there).