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?

  • $\begingroup$ 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." $\endgroup$ – Mark Fischler Apr 29 '19 at 21:59
  • $\begingroup$ Is the updated wording better? $\endgroup$ – Wesley Apr 29 '19 at 22:13
  • $\begingroup$ Much better. Now the answer could go either way. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.