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


2 Answers 2


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.

  • $\begingroup$ Thanks so much mixedmath! I'm seeing it now! $\endgroup$ Mar 13, 2012 at 5:10
  • $\begingroup$ Ahhh the satisfaction of a simple, elegant, piece of mathematical reasoning. $\endgroup$
    – t-tough
    Jan 31, 2021 at 15:31

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.

  • $\begingroup$ Thank You Very Much Andre - I understand it now! $\endgroup$ Mar 13, 2012 at 5:11

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.