I am supposed to solve the following problem by pigeonhole principle:
Peter solves at least one task per day for three months before the MO regional round. He does not solve more than $13$ tasks per calendar week. Prove that you can find several consecutive days during which student has solved, exactly $33$ tasks!
What I tried:
There is $12$ weeks in a $3$ months period. By this time, he is able to solve $12 \cdot 13= 156$ problems. But I do not know how to continue.
Can anyone help me?
Best Answer
This is not a solution to the current problem.
Using the standard setup, I will show that
In either case, this standard setup doesn't allow us to reduce the number of weeks.
I suspect the following statement is true (and possibly something stronger), as I cannot find a counter example:
3. With at most 13 tasks per calander week, over 13 weeks, then there is a series of days with exactly 33 tasks.
Note: Obviously if we're allowed 14 tasks per week, then we could do 2 a day and never get a series of days with exactly 33 tasks.
Proof of 1:
Let $t_i$ be the number of tasks done on day $i$.
Let $T_i = \sum_{j=1}^i t_j $ be the cumulative number of tasks done by day $i$.
We have $1 \leq T_1 < T_2 < \ldots < T_{105} \leq 195$.
Let our pigeons be $T_i$. There are 105 of them.
Let our pigeonholes be the sets of the form $\{ 66k + i, 66k+i+33 \}$. Since $66 \times 3 = 198 > 195$, there are 99 of them.
So, by PP, there are 2 piegons in 1 hole, which gives us $T_j = T_i + 33$.
Proof of 2.
Set up in a similar manner.
We have $1 \leq T_1 < T_2 < \ldots < T_{91} \leq 156$.
Let our pigeons be $T_i$. There are 91 of them.
Let our pigeonholes be the sets of the form $\{ 66k + i, 66k+i+33 \}$. Since $156 = 2\times 66 + 24$, there are $66 + 24 = 90$ of them.
So, by PP, there are 2 piegons in 1 hole, which gives us $T_j = T_i + 33$.
Thoughts on 3.
There are 91 pigeons and 99 holes.
We have 8 degrees of freedom in choosing the values of $T_i$.