Jessica the Combinatorics Student, part 2

The proof consists of two parts.

  • Part I: Prove that a period of $20$ days is enough such that there must exist some period of consecutive days during which totally $20$ hours are spent on studying.

  • Part II: A counterexample which shows that $19$ days are not enough is presented.


Proof of Part I

Let $x_1$, $x_2$, $\cdots$, $x_{20} \in \mathbb{N}^+$ denote the # of hours spent on studying for each day. In addition, put $$ f(i) = x_1 + x_2 + \cdots + x_i\quad\text{for}\quad 1 \leq i \leq 20 $$ to denote the total # of hours spent on studying before and on day $i$. Specially, $f(0) = 0$. It is easy to observe that $$ f(0) < f(1) < \cdots < f(20) $$ Let $$ A = \{f(0) + 20,\ f(1) + 20,\ \cdots,\ f(11) + 20\} $$ and $$ B = \{f(12),\ f(13),\ \cdots,\ f(20)\} $$

  • Because $$ f(11) = \color{red}{x_1 + \cdots + x_7} + \color{blue}{x_8 + x_9 + x_{10} + x_{11}} \leq \color{red}{11} + \color{blue}{11 - 3} = 19 $$ we have $$ A \subseteq \{f(11) + 1,\ f(11) + 2,\ \cdots,\ f(11) + 20\} \tag{1} $$

  • Because $$ f(20) = f(11) + \color{red}{x_{12} + \cdots + x_{18}} + \color{blue}{x_{19} + x_{20}} \leq f(11) + \color{red}{11} + \color{blue}{11 - 5} = f(11) + 17 $$ and $$ f(12) = f(11) + x_{12} \geq f(11) + 1 $$ thus $$ B \subseteq \{f(11) + 1,\ f(11) + 2,\ \cdots,\ f(11) + 17\} \tag{2} $$

There are totally $|A| + |B| = 21$ values but only $20$ slots, namely $f(11) + 1,\ \cdots,\ f(11) + 20$, exist by $(1)$ and $(2)$. Therefore, some $f(i) + 20 \in A$ and $f(j) \in B$ must equal. That is, $$f(i) + 20 = f(j)$$

$$\tag*{$\blacksquare$}$$


Proof of Part II

The counterexample is easy: Let the # of hours spent on studying every day be $1$.

$$\tag*{$\blacksquare$}$$



When the limit is $12$.

This part contains a proof for the case when the limit is $12$ instead of $11$.

In this case, let instead $$ A = \{f(0) + 20,\ f(1) + 20,\ \cdots,\ f(10) + 20\} $$ and $$ B = \{f(10),\ f(11),\ \cdots,\ f(20)\} $$ Because $$ f(10) = \color{red}{x_1 + \cdots + x_7} + \color{blue}{x_8 + x_9 + x_{10}} \leq \color{red}{12} + \color{blue}{12 - 4} = 20 $$ and $$ f(20) = f(10) + \color{red}{x_{11} + \cdots + x_{17}} + \color{blue}{x_{18} + x_{19} + x_{20}} \leq f(10) + \color{red}{12} + \color{blue}{12 - 4} = f(10) + 20 $$ we have $$ A \subseteq \{f(10),\ f(10) + 1,\ \cdots,\ f(10) + 20\} $$ and $$ B \subseteq \{f(10),\ f(10) + 1,\ \cdots,\ f(10) + 20\} $$ So totally $|A| + |B| = 22$ elements and $21$ slots. Thus Pigeonhole principle applies.


Here's code to run an exhaustive search, which confirms your suspicion that the answer is $20$ days.

Interestingly, it's still $20$ days if Jessica is allowed to work up to $14$ hours in any $7$-day period. If she's allowed to work $15$ hours, a repeating pattern of $5,1,1,1,5,1,1,1,\ldots$ avoids any sums of $20$ for any number of days.


This is in response to @joriki's observation that the constraint of the weekly total studying hours could be loosen while the conclusion of minimum $20$ days would still hold. I am not sure if it's appropriate to post this as an answer, but it turns out to be too long to fit in the comment section.

We shall prove the following, by using a slightly different pigeonhole construction than what's in the nice answer by @NP-hard:

(apologies for the slight notation change)

Suppose $m,n$ are positive integers and $$0=S_0<S_1<\ldots<S_n$$ is a sequence of integers that satisfy: $$\tag{1}S_{i+7}\le S_i+m\label{1},$$ for all $0\le i\le n-7$, then there exists $0\le j<k\le n$ so that $S_k-S_j=20$ if
$(1)~m\le 13$ and $n\ge 20$; or
$(2)~m=14$ and $n\ge 26$.


We prove the following lemma first:

If $$\tag{2}S_{i+20}<S_i+40\label{2}$$ for any $0\le i\le n-20$, then $S_k-S_j=20$ for some $0\le j<k\le i+20$.

Proof of the lemma:

Note if any $S_l=S_i+20$ for $i+1\le l\le i+20$, we can take $(j,k)=(i,l)$; otherwise consider the following $19$ integer subsets:

$$\{S_i+1,S_i+21\}, \{S_i+2,S_i+22\}, \ldots, \{S_i+19,S_i+39\}$$

and $20$ distinctive values of $S_{i+1}, S_{i+2}, \ldots, S_{i+20}$, by the pigeonhole principle, we conclude that there exists $i+1\le j<k\le i+20$ with $S_k$ and $S_j$ residing in the same subset, i.e., $S_k-S_j=20$.

Note we have not yet used the constraint \eqref{1}.

added: as @Shagnik pointed out, the proof above can be simplified by considering instead $20$ subsets $\{S_i,S_i+20\}, \{S_i+1,S_i+21\}, \ldots, \{S_i+19,S_i+39\}$ along with $21$ values $S_i, S_{i+1}, \ldots, S_{i+20}$.


Proof of the original propositions:

$(1)~m\le 13$, then

$$S_{20}\le S_{13}+m\le S_6+2m<S_7+2m\le S_0+3m<S_0+40,$$

by repeatedly applying \eqref{1}. We are done by taking $i=0$ in \eqref{2} and applying the lemma.

As @NP-hard pointed out, $n=19$ does not suffice as $S_i=i$ is a counterexample.

$(2)~m=14$, by the lemma, we only need to consider the case when

$$\tag{3}S_{i+20}\ge S_i+40\label{3}$$

for all $0\le i\le 6$. We have on the one hand

$$S_{10}\stackrel{\eqref{1}}\le S_3+14\stackrel{\eqref{3}}\le S_{23}-26\stackrel{\eqref{1}}\le S_2+16\stackrel{\eqref{3}}\le S_{22}-24\stackrel{\eqref{1}}\le S_1+18\stackrel{\eqref{3}}\le S_{21}-22\stackrel{\eqref{1}}\le 20$$

and on the other hand

$$S_{10}\stackrel{\eqref{1}}\ge S_{24}-28\stackrel{\eqref{3}}\ge S_4+12\stackrel{\eqref{1}}\ge S_{25}-30\stackrel{\eqref{3}}\ge S_5+10\stackrel{\eqref{1}}\ge S_{26}-32\stackrel{\eqref{3}}\ge S_6+8\stackrel{\eqref{1}}\ge S_{20}-20\stackrel{\eqref{3}}\ge 20,$$

therefore $S_{10}=20$, i.e., we can take $(k,j)=(0,10)$ in this case.

For $n=25$, one counterexample is

$$\left\{S_i\right\}=\left\{1,2,3,4,5,13,14,15,16,17,18,19,26,27,28,29,30,31,32,40,41,42,43,44,45\right\}$$

or in terms of daily studying hours:

$$\left\{1,1,1,1,1,8,1,1,1,1,1,1,7,1,1,1,1,1,1,8,1,1,1,1,1\right\}.$$


added: regarding @Joffan's counterexamples for $n=25$, the way we came up with the case above is by similarly applying \eqref{1} and \eqref{3} to prove that $S_i\le 2i$ for all $i\le 25$ except $i\in\{6,13,20\}$ when $S_i\ge 2i$ (as the inequality chain above now breaks into two at $S_{26}$). In addition, the set $\{S_0+20,S_1+20,\ldots,S_i+20,S_{10},S_{11},\ldots,S_{10+i}\}$ is precisely $\{10,11,\ldots,20+2i\}$ when $i\notin\{3,6,10,13\}$. These constraints above allow us to check handful cases and would be useful in general cases (e.g., when $20$ is replaced by some larger number and computer search could be infeasible).