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?
On
A proof by contradiction approach is helpful here. Let's try to prove that there is no $i$ and $j$ that work. In particular, we want to show that there is some arrangement that for every $i$ and $j$ the sum will not equal 10.
Let $x_1, x_2, ..., x_{60}$ be the number of books Charlie read in each month. Then we want to show that any sum $\sum_{n = i}^{j}x_n > 10$ or $\sum_{n = i}^{j}x_n < 10$. Try to find the smallest sequence that can't be smaller than 10. Then it must be larger than 10! But is there some reason that can't be true for all the sequences of that length? The Pigeonhole Principle may be helpful here.
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$.