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

pigeonhole-principle

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.

Best Answer

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

Related Question