# Pigeonhole Principle Problem

Problem: In the following 30 days you will get 46 homework sets out of which you will do at least one every day and - of course - all during the 30 days. Show that there must be a period of consecutive days during which you will do exactly 10 homework sets!

Solution: Let $$f_n$$ denote the number of homeworks from day $$1$$ to day $$n$$, where $$n\le 30$$. So, let us consider from $$f_1$$ up to $$f_{11}$$. There are ten possibilities for the remainder when each is divided by $$10$$. By the pigeonhole principle, there must exist two that have the same remainder, call these $$f_i$$ and $$f_j$$, for some $$i,j\in [1,11]$$. Therefore $$f_i - f_j \equiv 0 \pmod{10}.$$ But also $$f_i - f_j \not = 20$$. Hence $$f_i - f_j = 10$$.

I think this is on the right track. However, I have not convinced myself that $$f_i - f_j \not = 20$$

• I don't think you can rule out the possibility that $f_i-f_j=20$. Fortunately, you don't have to. If that's the case, then do the same analysis with the next $11$ days. There aren't enough homework sets for you to hit $20$ twice. – Robert Shore Apr 29 at 19:24

In fact, you would have to consider the case where $$f_i-f_j=20$$. Which might be messy...
You could alternatively do the following: we know that $$1\le f_1 Observe now that we are considering $$60$$ postive integers $$f_1,f_2,\ldots ,f_{30},f_1+10,f_2+10,\ldots , f_{30}+10$$ where all of them are less than $$57$$. By the Pigeonhole principle, at least $$2$$ numbers must be equal.
Therefore, we must have one integer from the first inequality being equal to another integer from the second inequality, since both inequalities are strictly increasing. Hence $$f_i=f_j+10$$ for some $$i,j\in\Bbb N_{<31}$$. Which is exactly what we wanted to prove.