A fun little math problem today. It came about when I misheard a problem asked by a friend, and solved a slightly different problem. It goes as follows:
A child watches television everyday. He always watches at least one hour a day, and he only watches tv in whole integer amounts of hours. Concerned for his well-being, his parents impose a restriction: he can never watch more than 11 hours of tv in any 7 day period. Show that there is some consecutive string of days in which the child watches exactly 20 hours of tv.
The number 20 is a relic of the problem that I misheard (show that this happens in any 11 week period). Of course, why stop there? Show that for any positive integer , there is some string of consecutive days in which he watches exact hours of tv.
This begs an interest question: for what other ‘restrictions’ is this property true? That is, what other numbers and have the property that if the child can only watch hours of tv in a day span, then he achieves every positive integer as a consectutive total?
I’ll review my proof of the original problem for any number first. We have the list of hours the child watches each day, and we want to find a consecutive substring whose total in . First, note that the child can never watch more than 5 hours of tv in a day. Otherwise, he couldn’t watch 1 hour each of the next 6 days and still stay under 11.
Next, let us proceed in the most naive possible way. We pick some starting day, and we keep a running total of the amount of tv watched since that day. We stop once the total is bigger than or equal to . However, since the previous day’s total was less than , and the child can’t watch more than 5 hours in any day, we know that this final total is between and . We could try to fix this overage by removing some of the first days, but in general we know nothing about them.
So now lets suppose that there is some string of 4 days in which the child watches only 1 hour each day. If we start counting on the first of these days, then no matter what the final total is, we can cut off some of the first days and get a total of exactly .
Of course, theres no reason to suspect that we can find four 1’s in a row. We can still use arguments of this type in the following way. If we have a string of 1’s of some length, we can start counting at the first one. Either the total is close enough to that we can fix it by cutting off some days, or the last day counted had a large number on it. However, if there is a single day with alot of tv, then all the surrounding days must have very small amounts in them; in particular, there will be a chunk of 1’s in a row. We can put all this together into a kind of ‘reverse’ induction.
If there are 4 ones in a row, its solved (by the above paragraph).
If there are 3 ones in a row, either the final total is less than or equal to (in which case some of the first days can be removed) or the final total is . This means that the child watched 5 hours of tv on the last day. However, if he watched 5 hours of tv on some day, then the next 6 days must all be ones.
If there are 2 ones in a row, either its solvable or the last day is at least 4 hours. This means the next 6 days can have at most 7 hours of tv. Therefore, there is at least one string of 3 ones in a row.
If there a single one, then either is solvable or the last day is at least 3 hours. This means the next 6 days can have at most 8 hours of tv. Therefore, there is at least one string of 2 ones in a row.
There must be at least one day the child watches exact one hour of tv.
Therefore, we can wind through the induction and always find some string of total exactly .
One annoying thing about this proof is that it seems pretty inefficient, in terms of bounding the number of days one needs to check. A quick estimate shows that one needs to check days before finding a sum up to . This is because for each starting day, we need to figure out the maximum number of days before the total is above . However, if this takes a long time, it means lots of the intervening days were ones, and we don’t need to work so hard to force there to be lots of ones in a row. Therefore, its clear that we can bring down this bound alot, but it would require alot of special arguments. In particular, I doubt a method of this form could be effective for computing sharp bounds.
So the next logical question is: what other pairs of numbers have this property? Certainly, I have no idea how to answer the question in general, but we can see for which numbers does the above proof work.
Let be the number of hours of tv the kid is allowed to watch in any day period, for fixed integers and . Also, let , the maximum number of hours the kid can watch in any day.
So now lets assume we can find ones in a row. Then starting with the first one, we get some total which we can fix as long as it is less than or equal to . If the total is more than , then the final day counted must be at least . This means that the next days have only hours maximum. After assigning the minimum one hour to each day, there are only hours left to play with. This forces there to be at least ones in a row somewhere (where is rounds the fraction up).
As long as , then the reverse induction from before will still work (because it will always force increasingly large strings of ones). Moving terms around gives . Since the coefficient of is positive and the vertex of the parabola is at , this will only be true for all positive if the discriminant is negative. This means that . Heuristically, this means that as the number of days in the restriction gets larger, the number of ‘extra’ hours can only increase like .
Of course, I’m sure that this property is true for all sorts of that this method doesn’t show. Can anyone think of examples?