7
$\begingroup$

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$

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Robert Shore Apr 29 at 19:24
15
$\begingroup$

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<f_2<\ldots<f_{30}=46\iff 11\le f_1+10<f_2+10<\ldots <f_{30}+10=56$$ 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.

$\endgroup$

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.