Chess Master Problem

Question

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! :D

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.

Answer 1

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

Answer 2

He has $11$ weeks of training (or $77$ days). The minimum and maximum number of games for this period is $77$ and $11 \cdot 12=132$, respectively.

We have distinct situations:

1) At any period of $k$ consecutive days he plays at least $k$ games. As well you asked.

2) The smallest period of $n$ days such that he plays $k=22$ games occur when he consider a week with a maximum number of games $12$ plus days after and before this week with a maximum possible number of games. Notice that in one day is possible to play $6$ games. So, take one day with $4$ games, one week with $12$ games, and one more day with $6$ games. You get then $22$ games in $9$ days.

Using 1) and 2) we conclude that between $9$ and $k$ days we always can make the choice of $22$ games.

I guess it is very useful!