Pigeonhole Principle Question: Jessica the Combinatorics Student

Jessica is studying combinatorics during a $7$-week period. She will study a positive integer number of hours every day during the $7$ weeks (so, for example, she won't study for $0$ or $1.5$ hours), but she won't study more than $11$ hours in any $7$-day period. Prove that there must exist some period of consecutive days during which Jessica studies exactly $20$ hours.

Here are my thoughts so far: Let $f(n)$ represent the total number of hours Jessica has studied after day $n$. Clearly, there are $49$ days in total, and the domain of $f$ is integers in the interval $[0,49]$. Proving that there must exist some period of consecutive days during which Jessica studies exactly $20$ hours is equivalent to proving that there must exist $i$ and $j$ such that $f(i)-f(j)=20$.

This is a really interesting question, but I don't see a clear path forward. How do you solve this question? Please try not to use extremely advanced math or I won't understand :P

Solution 1:

HINT: Let $S=\{f(k):k=0,\ldots,49\}$; you want to show that there is some $k$ such that $f(k)+20\in S$. (You want to allow $k=0$ to cover the possibility that some $f(k)=20$; $f(0)$ is of course $0$.)

You know that $f(49)\le 7\cdot11=77$, so all of the $100$ integers $f(k)$ and $f(k)+20$ for $k=0,\ldots,49$ are in the range $[0,97]$. However, there are only $98$ integers in that range. Can you see how to apply the pigeonhole principle to get the desired result? I’ve finished the argument in the spoiler-protected block below.

Clearly some two of the $100$ integers $f(k)$ and $f(k)+20$ must be equal. But the integers $f(k)$ are all distinct from one another, since she studies at least $1$ hour each day. This means that the integers $f(k)+20$ are also all distinct from one another. Therefore it must be the case that some $f(k)$ is equal to some $f(\ell)+20$, which means that on days $\ell+1$ through $k$ she studied a total of exactly $20$ hours.

Solution 2:

OK this was an interesting problem in itself, and the pigeonhole principle is implicit in practically any argument, so I just felt I would try to reason it out directly. With all kudos to Brian M Scott's more "hands-off" solution.

I'll proceed by trying to devise a schedule that allows Jessica to beat the expectation of a run of days with a 20-hour study total.

First observe that Jessica will not study more than 5 hours in one day, since she studies at least 1 hour every day, and no more than 11 hours in a seven-day period (so she only has 4 hours excess over the minimum study of $7 \times 1$ hour per day).

Next note that this means that any run of 4 consecutive single-hour study days means that we can find a run of days with total study time of 20 hours, as follows: extend the 4 single-hour days out (forwards or backwards) until the total study time reaches or exceeds 20 hours. The maximum possible total at this point is 24 hours, due to the 5-hour maximum per day. Then shorten the range by discarding from the single-hour study days until 20 hours is achieved.

Now note that a 5-hour study day will actually mean that the adjacent period has a run of 6 single-hour study days. So we need not consider any sequence with a 5 hour study day further.

So the working maximum study day is now 4 hours, which means a run of 3 single-hour study days will automatically allow us to find a 20-hour run of days, as before. But the 6 days after/before a 4-hour day must contain a run of 3 single-hour study days, so a 4-hour study maximum will also lead to a 20-hour run.

So now consider a 3-hour limit on study per day. Now this means that an run of 2 successive single-hour study days will allow finding a 20-hour run as before, and a 3 hour study day will mean that the 6-day period before and after has only at most 8 hours to allocate to those days, which will inevitably generate successive single-hour study days.

Finally a 2-hour study limit per day only requires, under the previous construction, that there is a single day somewhere with only one hour studied, and we know from the pigeonhole principle that there are at least 3 such days in every 7-days period - quite apart from the fact that studying 2 hours every day would easily allow us to find a 20-hour run in any case.

The above construction implies that the 7-week course length is significantly more than is necessary to force the existence of a run of days with a 20-hour study total.

Solution 3:

Hint: Show that there exist at least two disjoint periods in each of which the total number of hours spent for combinatorics is $0$ modulo $20$. Prove that one of them must have exactly $20$ hours (by verifying that not both periods can have at least $40$ hours).