# How are the pigeonholes calculated in this pigeon-hole problem?

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

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.

• 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.

• Thank You Very Much Andre - I understand it now! – Adel Mar 13 '12 at 5:11