A social worker has 77 days to make his visits. He wants to make at least one visit a day, and has 133 visits to make. Is there a period of consecutive days in which he makes a.) 21 b.) 23 visits? Why?
a.) Set $a_i$ to be the number of visits up to and including day $i$, for $i = 1,\dots, 77$. Then if we combine the set of all $a_i$ with the set $\{ a_1+21,a_2+21,\dots,a_{77}+21 \}$, then we have $77\cdot2=154$ numbers, less than or equal to $133+21 = 154$. Thus we see by the pigeonhole principle that we might have that not any of these 154 numbers to be identical. So there isn't necessarily a period of 21 days.
b.) No, since $23>21$, it follows from a.) that this wouldn't work.
Is this correct thinking? Being somewhat superstitious, I feel that at least one should be correct.. Thanks
Consider the cumulative number of visits $a_i$ after day $i$, taken $\bmod 21$. We can also include $a_0=0$ here. Then by the generalized pigeonhole principle there is some residue class with at least $\lceil 78/21\rceil =4$ values in it. Furthermore, if there are no classes with $5$ or more values then there are at least $78-3\times 21 = 15$ such residue classes which have $4$ values.
Now since $133<7\times 21$, any residue class with $5$ or more values must have $2$ of those values separated by only $21$. For the values $126$ to $133$, $8$ values in all, these can support $4$ residue values without having values separated by only $21$, but we would then have another $7$ cases of $4$ values in a residue class with only $6$ distinct values in range, giving that these must have values separated by only $21$.
For $23$ the argument is similar but simpler. Taking the values $a_i \bmod 23$, we see that there must be some residue classes with $4$ or more values in, and since $133< 6\times 23$ such residue class sets must include values that are only $23$ apart.