Question 1113831: 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.
Answer by math_helper(2461)   (Show Source):
You can put this solution on YOUR website!
Sorry, this is not a full solution. I'm pretty sure this problem lends itself to the pigeonhole principle (if there are n pigeonholes and n+1 pigeons, at least one pigeonhole must have 2 or more pigeons).
—
First, reduce the possible 7-day sums… I use "week" to denote any 7 consecutive days:
The weeks consisting of exactly 7 hours {1,1,1,1,1,1,1} can be eliminated because if there were such a week, one could start summing, say, immediately after (before) that week and work right (left) summing values until it was just less than 20. Then, by including a select number of days from the week of 7 hours, they could make the sum equal to 20.
Note that the sum can be brought to within 4 of 20 (  ) no matter how many hours there are in a given week. This is so because the maximum value that can appear on any given day is 5 hours, and to have a day with 5 hours means you will have {1, 1, 1, 1, 1, 1, 5, 1, 1, ,1 , 1, 1, 1 }, i.e. at least 6 ones to the left AND right of the 5 ("she won't study more than 11 hours in any 7-day period").
Using a similar argument, weeks summing to 8 or 9 hours can also be eliminated. That is, their presence would easily allow one to reach a sum of 20. Here are the 8 and 9 hour possibilities:
8 hours: { 2, 1, 1, 1, 1, 1, 1 } and the 6 permutations.
9 hours: {3, 1, 1, 1, 1, 1, 1 } and 6 permutations, plus { 2, 2, 1, 1, 1, 1, 1 } and its permutations.
Each of these (8hr weeks, 9hr weeks) can make up the difference in  to make it exactly 20, due to the high concentration of ones in the partition. Yes, this is a little hand-waving, but I think it is correct. [ With the 9hr weeks, it may be required that the sum be adjusted downward by chopping values from the right (left) then including more values from the week of 9hrs as needed to make it sum to 20. ]
—
Thus, we have only weeks summing to 10 or 11 hours left to consider. Here I think the pigeonhole principle can be used, but I have trouble identifying the pigeons and pigeonholes (which is common in these types of problems). It might be possible to formulate a proof by contradiction as well, not sure.
—
Maybe another tutor wants to give this some thought and solve it. If you already have a solution, I'm interested to know how the solution was found. I found this problem to be interesting.
|
|
|
