A student is preparing for an exam. Show that there exists consecutive days such that the student learns exactly 4 hours.

Question

A student is preparing for an exam for $13$ days.

• In total, he prepares no more then $20$ hours.
• Every day he prepares a whole number of hours, and each day he prepares for at least one hour.
• Show that there are consecutive days where the student prepares a total amount of exactly $4$ hours. In other words, given $x_{1},\ldots, x_{13}$ such that $x_{i} \geq 1$ is a natural number for all $i$ and $x_{1}+ \cdots + x_{13} \leq 20$.
• Show that there exist $i,k$ such that $x_{i} + x_{i+1} + \cdots + x_{i + k} = 4$.

I was able to solve it by splitting into a lot of cases with the maximal value of preparation per day, but I don't know how to solve it using pigeonhole principle. Any idea ?. Thanks.

Answer 1

Let $E$ be the set $\{x_1,x_1+x_2,x_1+x_2+x_3,\ldots,x_1+x_2+\ldots+x_{13}\}$. $E$ is made by $13$ elements in $[1,20]$.
$E+4$ is made by $13$ elements in $[5,24]$, so if we assume that $E$ and $E+4$ are disjoint we get $$ 26=|E|+|E+4|=|E\cup(E+4)|\leq |[1,24]| = 24, $$ a contradiction. It follows that two elements of $E$ differ by $4$.

Answer 2

I think the result can be made a little stronger.

Suppose the student studies for $N$ hours in total. In sequence, name the hours $h_1,$ $h_2, \ldots, h_N.$ Construct pigeonholes as follows:

If $(k \bmod 8) \in \{1,2,3,4\}$ and $k+4 \leq N,$ make one pigeonhole from the two hours $h_k$ and $h_{k+4}.$

If $(k \bmod 8) \in \{1,2,3,4\}$, $k \leq N$, and $k+4 > N,$ make one pigeonhole from the single hour $h_k$.

Now any given pigeonhole can contain the first hour of study from only one day, because if both $h_k$ and $h_{k+4}$ are first hours of study in their respective days, the four hours $\{h_k, h_{k+1}, h_{k+2}, h_{k+3}\}$ are the hours of study on some day or sequence of consecutive days in which the student studied exactly $4$ hours.

If $N \leq 24$ there are then at most $12$ pigeonholes, and therefore the student can study at most $12$ days without studying exactly $4$ hours over some set of consecutive days.

In order to study $13$ days under the $4$-hour restriction, the student must study at least $25$ hours. But if the student studies $25$ hours it is possible to study for $13$ days without breaking the $4$-hour restriction. An example of the sequence of hours in such a case is $$ 1,1,1,5,1,1,1,5,1,1,1,5,1. $$

---

Note that if $N > 4$ we can delete the hour $h_{N-3}$ from its pigeonhole. If it was the only hour in that pigeonhole, we can delete the entire pigeonhole. For example, if the student studies $24$ hours in total, hour $h_{21}$ cannot be the first hour of study in a day. We did not need this fact to prove that $N>24$ for $13$ days of studying, but it might be useful for a variant of the problem with a different number of days.