7
$\begingroup$

The original question about Jessica, which I encourage review of, is as follows:

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.

My follow-up question is this:

How far into the course (how many days) do you need before you can be sure that Jessica has had some sequence of consecutive days with a twenty-hour study total?

My suspicion is that the answer is: twenty days. I think my answer at the original question can be used to demonstrate that four weeks is certainly enough

$\endgroup$
  • $\begingroup$ Didn't you answer this yourself in the original question? The number of days at least needed is 20, since otherwise we can have a row of ones. Then we apply your method of proof. In this sequence of twenty numbers you have checked all the possibilities and shown that indeed there must be a consecutive subsequence that sums to 20? $\endgroup$ – Marc Jul 12 '16 at 20:39
  • 1
    $\begingroup$ @Marc I didn't show that only 20 days are needed. The arguments I use there rely a bit on effects over a week, so I dare say that my original argument is good to prove 27 days, but not 20 (without additional work). $\endgroup$ – Joffan Jul 12 '16 at 21:53
1
$\begingroup$

I think this might essentially be a reformulation of Wiley's proof in the case when at most $13$ hours of study are permitted over a $7$-day period. However, the application of the pigeonhole principle is perhaps simpler.

For $0 \le i \le 20$, let $S_i$ be the total number of hours studied by the end of the $i$th day (setting $S_0 = 0$), and consider these values modulo $20$.

Since we have $21$ terms taking $20$ possible values, there are some $0 \le i < j \le 20$ such that $S_i = S_j$. It follows that the total number of hours of study between days $i+1$ and $j$ (inclusive) is a multiple of $20$.

If it is not exactly equal to $20$ hours, then it must be at least $40$ hours. However, this is over a span of at most $20$ days. Dividing this into three periods of at most $7$ days (say the first week, second week, and third week), by averaging we find that she must have worked at least $14$ hours during one of the weeks, which is not allowed.

Thus she must actually have studied exactly $20$ hours between days $i+1$ and $j$.

$\endgroup$
  • $\begingroup$ Yes, that's a little cleaner as route to Wiley's lemma.Thanks. $\endgroup$ – Joffan Jul 17 '16 at 23:05
  • $\begingroup$ @Joffan, agreed. It's indeed cleaner to use 20 "holes" with 21 "pigeons" rather than separating $S_l=S_i+20$ as an individual case in my proof. Thank you, Shagnik. $\endgroup$ – Wiley Jul 18 '16 at 3:59
6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ +1, nice proof. Am I right in thinking that it works only for the limit of $11$ and not for limits of $12$ to $14$, which my exhaustive search found to also be sufficient? $\endgroup$ – joriki Jul 15 '16 at 8:03
  • 2
    $\begingroup$ @joriki I do not know whether the proof can be adapted to the cases where the limit is $13$ or $14$. But the case where the limit is $12$ can be proved in a similar way. See my updates please. $\endgroup$ – PSPACEhard Jul 15 '16 at 10:41
  • $\begingroup$ Yes, nice technique, and perfectly in keeping with the pigeonhole principle that the original question was exercising. $\endgroup$ – Joffan Jul 15 '16 at 16:01
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, that's a very interesting split - either a 20-hour period must be in the first 20 days or there may be no such period. $\endgroup$ – Joffan Jul 11 '16 at 22:53
  • $\begingroup$ She works no more than 77 hours. So it is sufficient to show that every partitioning of the number 77 into 49 parts consists of a set of integers which cannot be sequenced to contain no partitioning of the number 20. $\endgroup$ – user334732 Jul 12 '16 at 17:19
  • 1
    $\begingroup$ @RobertFrost: I think that's a misunderstanding of the question. Your comment seems to refer to the original question linked to, not to the new question raised here, which doesn't refer to a $7$-week period, and thus isn't related to $77$ hours or $49$ parts. $\endgroup$ – joriki Jul 13 '16 at 0:02
  • $\begingroup$ @joriki yes sorry I'm answering the old question. $\endgroup$ – user334732 Jul 13 '16 at 6:20
  • $\begingroup$ @joriki, there might be a bug in your code, as it turns out that the answer of 20 days only holds for up to 13 hours in any 7-day period. For 14 hours, the answer should be 26 days. Details are in a separate answer, as it's too long to fit in the comment section. $\endgroup$ – Wiley Jul 16 '16 at 17:32
2
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice work, I like the Lemma especially, and the demonstration of a case where $20$ days are not enough but there is a solution with more days. $\endgroup$ – Joffan Jul 16 '16 at 18:35
  • $\begingroup$ There are 4 patterns for the limit case in the 14-hour case: $$(1, 1, 1, 1, 1, 7, 2, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 2, 7, 1, 1, 1, 1, 1)\\(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)\\(2, 1, 1, 1, 2, 5, 2, 2, 1, 1, 1, 2, 5, 2, 1, 1, 1, 2, 2, 5, 2, 1, 1, 1, 2)\\(2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 3, 2, 2, 1, 2, 2, 2, 3, 2, 2, 1, 2, 2)$$ $\endgroup$ – Joffan Jul 17 '16 at 4:10
  • $\begingroup$ @Joffan, thank you. Presumably these are all solutions from exhaustive search? $\endgroup$ – Wiley Jul 18 '16 at 5:09
  • $\begingroup$ Correct, I translated and extended Joriki's code. You can see the progression, but I wouldn't have expected a 3-hour maximum solution. $\endgroup$ – Joffan Jul 18 '16 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.