# Pigeonhole Principle Problem, where the principle doesn't work

Problem: 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. Must there always be a period of consecutive days in which he makes 23 visits? Why?

Using the pigeonhole principle didn't help me conclude anything, which leads me to believe that there is not a period of consecutive days where he makes 23 visits. But how would I prove this? With a counterexample?

• The wording of this question is terrible, because it gives away the answer, that there must be a period of consecutive days with $23$ visits. Because you can find one such example, namely visit 1 person for each of the first $23$ days. So if you could also have a pattern without such a set of consecutive days, then the answer would be "we can't tell if there is or is not." – Mark Fischler Apr 29 '19 at 21:59
• Is the updated wording better? – Wesley Apr 29 '19 at 22:13
• Much better. Now the answer could go either way. – Mark Fischler Apr 29 '19 at 22:30

Let $$a_k$$ be the cumulative number of visits starting with day $$1$$, where $$k$$ goes from $$1$$ to $$24$$. Then by the pigeonhole principle $$\exists~ 1 \leq i \lt j \leq 24 \text{ such that } a_i \equiv a_j \pmod{23}$$. Thus, the number of visits from day $$i+1$$ to day $$j$$ is a positive multiple of $$23$$. (It can't be $$0$$ because each day must include at least $$1$$ visit.)
Similarly, let $$b_k$$ count cumulative visits starting with day $$25~(k \leq 24)$$ and let $$c_k$$ count cumulative visits starting with day $$49~(k \leq 24)$$. Again, there is a period within those intervals where the total number of visits must be a multiple of $$23$$.
At least one of those three differences must in fact be $$23$$. Otherwise, we would have accounted for at least $$46 \times 3=138$$ visits and there aren't that many available.