For $5$ years, Charlie reads at least one book every month, but no more than $100$ books in total.
Show that there exist two integers $i$ and $j$, with $i < j$, such that the number of books read by
Charlie between month $i$ and month $j$ is exactly equal to $10$.
I thought we can find only the lower bound using pigeonhole principle. How can I find the exact amount of books?
Best Answer
Let $x_i$ be the number of books Charlie has read by the end of month $i$, $1 \leq i \leq 60$. Since Charlie reads at least one book each month, each $x_i$ is distinct, and $$1 \leq x_1 < x_2 < x_3 < \ldots < x_{58} < x_{59} < x_{60} \leq 100$$ Let $y_i = x_i + 10$, $1 \leq i \leq 10$. Then each $y_i$ is distinct, and $$11 \leq y_1 < y_2 < y_3 < \ldots < y_{58} < y_{59} < y_{60} \leq 110$$ Notice that the set $\{x_1, x_2, x_3, \ldots, x_{60}, y_1, y_2, y_3, \ldots, y_{60}\}$ contains $120$ values between $1$ and $110$, so they cannot all be distinct. Thus, there exist $i, j$ with $i < j$ such that $y_i = x_j$, which means $x_i + 10 = x_j$, so Charlie read exactly ten books between months $i$ and $j$.