Chess Master Problem

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.

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

Solution 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!

Solution 3:

You can generalize the method in the text slightly by restricting the search to subsets of the 77 days. As an example, to keep it simple, consider the first and last $n$ weeks:

Let $a_n$ be the total games played by the end of day $n$. Considering the first $n$ weeks, the totals for days $a_1,...,a_{7n}$ must take values in $[1,12n]$. Likewise, the final $n$ weeks $a_{7(11-n)+1},...,a_{77}$ must take values in $[7(11-n)+1, 132]$.

If we are looking for consecutive days totaling $k$ games then considering the set of $14n$ integers $$a_1+k, ..., a_{7n}+k, a_{7(11-n)+1},...,a_{77}$$ these must take values in $[\min(k+1,7(11-n)+1), \max(12n+k,132)]$ which is a set of $\max(12n+k,132)-\min(k,7(11-n))$ integers. Therefore, any time $$14n > \max(12n+k,132)-\min(k,7(11-n))$$ $$\Leftrightarrow 2n > \max(k, 12(11-n))-\min(k, 7(11-n)) = f(k,n)$$ then by the pigeonhole principle there must be an instance of $a_i+k=a_j$.

For there to be any solutions you must have $\min_{k}f(k,n) = 5(11-n)<2n$ i.e. $n \ge 8$, and indeed with $n=8$ you can prove the cases $k \in [21,36]$.

You may be able to do better than this by considering finer grained subsets.