1

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.

Felix Marin
  • 89,464
Omer
  • 2,490
  • 1
    Shouldn't it be that he prepares no more than $21$ hours? If he studies $2$ hours the first day, then $1$ hour the second day, continuing like this for alternate days, the question statement is not true. – Toby Mak Sep 22 '19 at 08:42
  • @Toby Mak why not true? take i = k = 2 – Omer Sep 22 '19 at 08:44
  • Yes, but the question has to hold for all possible arrangements. Draw it out and you'll see what I mean. – Toby Mak Sep 22 '19 at 08:47
  • 1
    @Toby Mak I don't understand. The question requires that there will be some i>=1 and k>=0 such that $x_i+x_{i+1}+...+x_{i+k}=4$. In your example we have i=k=2 works. Do you have an example where there are no such i,k? – Omer Sep 22 '19 at 08:58
  • What I mean is that $x_{i} = 2$ where $i$ is odd, and $x_i = 1$ when $i$ is even. And $x_2+x_{2+1}+x_{2+2}$ are three consecutive days. – Toby Mak Sep 22 '19 at 09:04
  • @Toby Mak yes, and these three consecutive days work. What is wrong with that? – Omer Sep 22 '19 at 10:31

2 Answers2

2

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

Jack D'Aurizio
  • 353,855
0

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.

David K
  • 98,388