0

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?

Wesley
  • 1,567
  • 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

1 Answers1

2

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.

Robert Shore
  • 23,332