Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The question is as follows:

To prepare for a marathon, an elite runner runs at least once a day over the next 44 days, for a total of 70 runs in all. Show that there's a period of consecutive days during which the runner runs exactly 17 times.

I know the mechanics of solving it. It is:

Let $r_i$ be the total number of runs as of day $i$.

$1 \le r_1 \le r_2 \le r_3 \ldots \le r_44 = 70$

Let's do $r_i + 17$

$18 \le r_1 + 17 \le r_2 + 17 \le \ldots \le r_44 + 17 = 70 + 17 = 87$

Now counting the pigeons:

$r_i$ is $44$ values

$r_i + 17$ is $44$ values. $44 + 44 = 88$ pigeons.

The pigeonholes are the $87$ values available. So by the pigeonhole principle

$r_i = r_j + 17 \le i > j$ (I don't really get this part).

My main issue is how are the pigeons calculated to be $44 + 44.$

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Let's consider this solution in more detail.

So we have the 44 $r_i$, namely $r_1, \ldots, r_{44}$. We know that each $r_i$ is bounded by $1$ and $70$, and that exactly $44$ different values are taken (since there are $44$ $r_i$, and they can each be at most one thing).

Suppose we consider $s_i = r_i + 17$. Again, we have 44 different $s_i$, namely $s_1, \ldots, s_{44}$. And each $s_i$ is bounded by $18$ and $87$. Similarly, exactly $44$ values are taken.

Thus there are $44$ different $r_i$ and $44$ different $s_i$, so we have $88$ 'pigeons.' However, the largest element ($s_{44}$) is $87$. So our $88$ values lie in the $87$ numbers from $1$ to $87$. These are the 'holes.'

And then the principle is applied.

share|improve this answer
    
Thanks so much mixedmath! I'm seeing it now! –  Adel Mar 13 '12 at 5:10

There is a minor mistake in the typing of the question. This may be a source of misunderstanding. Since the runner runs at least once a day, the sequence $r_1, r_2, r_3 \dots$ is strictly increasing. You had $r_1\le r_2\le r_3$ and so on, and should have instead $r_1<r_2<r_3$ and so on, with similar inequalities for the $r_i+17$. This makes a big difference later in the analysis.

There are only $87$ possible values for the $r_i$ and the $r_i+17$, yet there are $88$ items mentioned ($44$ of each kind). So two of the items must be equal.

We cannot have $r_i=r_j$ where $i\ne j$, because the $r_i$ are increasing. The same applies to the $r_i+17$, for the same reason. So there must be an $r_i$ and an $r_j+17$ which are equal. Could we have $i\le j$? Certainly not, because if $i \le j$, then $r_i+17 \le r_j+17$, so we cannot have $r_i=r_j+17$.

So $i>j$. But then since $r_i=r_j+17$, we have $r_i-r_j=17$, so in the period from day $j+1$ to day $i$ inclusive, the runner must have run exactly $17$ times.

share|improve this answer
    
Thank You Very Much Andre - I understand it now! –  Adel Mar 13 '12 at 5:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.