11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ When you say a succession of consecutive days, do you mean two, seven, fourteen, or some other amount of days? $\endgroup$ – InterestedGuest Dec 30 '10 at 10:03
  • $\begingroup$ Like I said in the question: k games, k >= 22. I'm essentially asking for a general proof for the case k >= 22. $\endgroup$ – K-RAN Dec 30 '10 at 10:06
  • 3
    $\begingroup$ I am not asking the amount of games he will play, I am asking the span of the consecutive days. Two consecutive days for 22 games? 14 consecutive days for 22 games? If it's two consecutive days, it can be easily proven that he won't be able to play 22 games. 14 days (for example), different story. :) $\endgroup$ – InterestedGuest Dec 30 '10 at 10:07
  • 1
    $\begingroup$ So pretty much any number of consecutive days, as long as he plays more than or equal to 22 games? That's very easy (and probably not what you are looking for), see my answer. $\endgroup$ – InterestedGuest Dec 30 '10 at 10:11
  • 1
    $\begingroup$ @K-RAN, since he has to play at least a game a day, after 22 days he will have played 22 games, so $k$ holds true. $\endgroup$ – InterestedGuest Dec 30 '10 at 12:05
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The problem is that, while working on this problem, my friend wrote a program to figure out all possible schedules that the chess master can make. Not once did a counter example come up (he started with k = 24 or 25). Either way, thanks a lot! This is the explanation that I was looking for. +1 for clearness :D $\endgroup$ – K-RAN Dec 30 '10 at 19:43
  • $\begingroup$ @K-Ran: It is possible, I was only guessing the non-existence. For instance, if you consider the proof for $k=24$, you will see that there is a lot of scope to increase $k$. Of course, this case-by-case proof is unenlightening, maybe there is a proof which will cover all cases... (the restriction to use pigeonhole might make it harder though). $\endgroup$ – Aryabhata Dec 30 '10 at 20:05
4
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

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