KingGeorge 3 years ago KingGeorge's Challenge of the Month! [SOLVED BY @ganeshie8] Your roommate, Bob, watches at least 1 hour of TV per day, but no more than 11 hours per week, and only in hour increments. Show that in the next seven weeks, there exists some period of consecutive days where Bob watches exactly 20 hours of TV.

1. zzr0ck3r

2. experimentX

*

3. anonymous

All right, although I can't give a rigorous proof for this (haven't come up with one, yet), I can give a simple argument over why it works. In any week, the maximum of the sum of any one day is 5 hours, if we place three consecutive weeks containing this day in one extreme, the remaining amount of days for each week is one, thus we may choose from six other days to add an amount less than or equal to six (because there are six remaining days of the week which each have one hour), without adding the 5 at one extreme in one of the weeks, yet we can choose a specific amount throughout which can be, at most, one greater than 5. By this, given 7 weeks, we can always construct 20 in sums of consecutive days, if every day holds at least an hour, and the total of the weeks can be at most 11. :) I like the problem, I'm still trying to come up with a more rigorous solution...

4. KingGeorge

Just a note, the rigorous solution I have to this problem, is rather elegant, but there are two key observations one must make to solve it this way. If it is still unsolved, I will post a hint tomorrow.

5. mathslover

I promise I am not a "challenge lover" though I will wait for the hint...

6. KingGeorge

Also, I'm not following your argument @LolWolf

7. anonymous

Hmm... it's a little convoluted, but, I'll just wait for the hint to give a definitive, cleaner answer (*if* I can solve it, of course...)

8. ganeshie8

\(d_{49} \le 11*7 = 77\)

9. ganeshie8

call \(d_n\) hours TV watched till \(n\)th day \(1 \le d_1 < d_2 < d_3. ....... < d_{49} \le 77\)

10. ganeshie8

see that above is strictly increasing "\(d_1 - d_{49}\)" hence, below is strictly increasing too \(21 \le d_1+20 < d_2 + 20 < d_3+20 ...... < d_{49}+20 \le 97\)

11. ganeshie8

Now take the two sequences together, \(1 \le d_1 < d_2..... < d_{49} \ AND\ d_1 + 20 < d_2 + 20..... < d_{49}+20 \\ \le 97\) we have two sequences, each of them distinct, and 49*2 = 98 total terms. we need to assign 98 terms to (1-97) integers. now we can apply pigeonhole principle and prove the thing easily 98 pigeons, 97 holes

12. KingGeorge

Perfect. That's almost exactly the solution I have. Could you give a quick explanation of why you used \(d_1+20,d_2 + 20,d_3+20, ......, d_{49}+20\)? (For the benefit of the other readers)

13. ganeshie8

KingGeorge i see 20 hours constraint coming from "77 hours in 49 days" i feel you will explain it in a better way than me....

14. KingGeorge

Very well. Consider the sets \[D_1=\{d_1,d_2,...,d_{49}\}\]\[D_2=\{d_1+20,d_2+20,...,d_{49}+20\}\]\[A=D_1\cup D_2\]Where \(d_i\) was defined above by @ganeshie8. Note that if \(D_1\cap D_2\neq\emptyset\), then there exists some \(d_r,d_s\) such that \(d_s=d_r+20\). This implies that in the days \(r+1, r+2, ..., s\) Bob watched exactly 20 hours of TV.

15. KingGeorge

Now, note that since these are all distinct since Bob watches at least 1 hour per day. So we have that \(1\le d_1\) and \(d_{49}+20\le 97\), and \(d_{49}+20\) is the maximum of set \(A\). So we have a set with 98 elements, and 97 numbers to choose from. Therefore, we have a repeated number by the pigeonhole principle. Since \(D_1\) has no repeats by definition, as well as \(D_2\), it must be that \(D_1\cap D_2\neq\emptyset\), so we are done.