6
$\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$
1
  • 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$ Apr 29, 2019 at 19:24

1 Answer 1

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$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .