1
$\begingroup$

A man can drink at least one cup of coffee at the day. After one year he drinks 500 cup of coffee. Need to prove that there is a continuous sequence which contains 100 cup of coffee, i.e. a man drinks one cup of coffee at the day. I suppose that the task somehow is connected with the finding of the monotone paths.

$\endgroup$
  • $\begingroup$ If he can drink one cup of coffee per day, how is that after a year he drinks more than $366$ cups of coffee? There must be something wrong. $\endgroup$ – Crostul Jul 20 '16 at 7:21
  • $\begingroup$ Presumably this is a sequence of $365$ positive integers $X_i$, with $\displaystyle S_j=\sum_{i=1}^j X_i$ where $S_0=0$ and $S_{365}=500$ and you want to show that there must exist $j,k$ with $S_j-S_k=100$ $\endgroup$ – Henry Jul 20 '16 at 7:25
  • $\begingroup$ At least one cup of coffee. $\endgroup$ – Վարդան Գրիգորյան Jul 20 '16 at 7:26
  • $\begingroup$ Henry- Yes thats it, how can it be done ? $\endgroup$ – Վարդան Գրիգորյան Jul 20 '16 at 7:27
  • 1
    $\begingroup$ Similar math.stackexchange.com/questions/820425/… $\endgroup$ – Henry Jul 20 '16 at 7:38
3
$\begingroup$

If the number of cups of coffee drunk on the $i$th day is $X_i$ and $\displaystyle S_j=\sum_{i=1}^j X_i$ then $S_0=0$ and $S_{365}=500$.

Now consider the set $\{S_0,S_1,S_2,\ldots,S_{365}\}\cup\{S_0+100,S_1+100,S_2+100,\ldots,S_{365}+100\}$

The union has at most $601$ distinct elements even though each of the two subsets has $366$ distinct elements and $601<2×366$ so there must be a duplicate pair by the pigeonhole principle

As the elements in the first subset are all distinct, as are those in the second half, a duplicate pair must have one term of the form $S_j$ and the other of the form $S_k+100$, in which case $S_j-S_k=100$ and so $100$ cups were drunk from the $k+1$th day through to the $j$th day

$\endgroup$
  • $\begingroup$ It would be better to say that the union has at least $730$ elements since we need to know that there are at least $601$ elements (the smallest number is at least $1$ since he drinks at least one cup of coffee a day) in the union in order to draw the desired conclusion. $\endgroup$ – N. F. Taussig Jul 20 '16 at 9:09
  • $\begingroup$ @N.F.Taussig: Or perhaps say that the union has at most $601$ distinct elements even though each of the two subsets has $366$ distinct elements and $601 \lt 2 \times 366$ $\endgroup$ – Henry Jul 20 '16 at 18:34
  • $\begingroup$ I like the formulation in your comment more than the one in your original answer since "potentially up to $732$ elements" could be less than $600$. $\endgroup$ – N. F. Taussig Jul 20 '16 at 18:44
  • $\begingroup$ @N.F.Taussig - thank you - I have edited it $\endgroup$ – Henry Jul 20 '16 at 18:54

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.