I find the following mind-boggling.

Suppose that runner $R_1$ runs distance $[0,d_1]$ with average speed $v_1$. Runner $R_2$ runs $[0,d_2]$ with $d_2>d_1$ and with average speed $v_2 > v_1$. I would have thought that by some application of the intermediate value theorem we can find a subinterval $I\subseteq [0,d_2]$ having length $d_1$ such that $R_2$ had average speed at least $v_1$ on $I$. This is not necessarily so!

Question. What is the smallest value of $C\in\mathbb{R}$ with $C>1$ and the following property?

Whenever $d_2>d_1$, and $R_2$ runs $[0,d_2]$ with average speed $Cv_1$, then there is a subinterval $I\subseteq [0,d_2]$ having length $d_1$ such that $R_2$ had average speed at least $v_1$ on $I$.

  • $\begingroup$ Lingering in the background, is the question, whether there is such a "global constant" $C>1$ as asked for in the question. I think there must be, but I haven't been able to prove it... $\endgroup$ – Dominic van der Zypen Dec 5 '18 at 14:48
  • 10
    $\begingroup$ Is the runner allowed to run backward? $\endgroup$ – Robert Israel Dec 5 '18 at 15:01
  • 3
    $\begingroup$ I don't find this so bind-boggling: if $d_1$ is bigger then $d_2/2$, then there is a subset $S$ of $[0,d_2]$ included in every subinterval of length $d_1$. If the second runner is very slow on $S$, for example it needs more time than the total time for the first runner (meaning that it must be very fast outside $S$ to be faster, on average, then the first runner) we have the required situation. $\endgroup$ – Ricky Dec 6 '18 at 21:21

The constant is $2$. Let $n=\lfloor d_2/d_1 \rfloor \geq 1$, and let $t_k$ be the time which the long distance runner takes to arrive at the distance $kd_1$ from the origin, $1\leq k\leq n$.

Proving by contradiction, suppose that on every interval $[(j-1)d_1,jd_1], j=1,...,k$ the average speed of the long distance runner is less than $v_2/2$. Then $t_n>2nd_1/v_2$. On the other hand the total time of the long distance runner is $d_2/v_2\geq t_n$. Therefore $$2nd_1 < t_n v_2 \leq d_2 \leq (n+1)d_1,$$ which implies $n<1$, a contradiction.

It is easily seen that $2$ is best possible. Let $d_1=d_2/2+\epsilon$ where $\epsilon>0$ is small. Let the long distance runner run with very high speed for half of the distance, then stop (or run very slowly), and then run with the same high speed to the end. The average speed on every interval of length $d_1$ is close to $1/2$ of the overall average speed.

The same argument proves that $C\leq 1+1/n$ when $n$ is known. Also notice that when $d_2$ is divisible by $d_1$, one can take $C=1$.

Remark. However, this does not solve the problem completely. A complete solution would be the optimal constant $C(d_2/d_1)$ for any given ratio $d_1/d_2$.

Edit. I suppose that $C(x)$ is the following: $C(n)=1$ for every integer $n\geq 1$, $C(n-0)=n/(n-1)$ (these two properties have been proved above), and $C$ is linear between consecutive integers. In particular $C(x)=x$ for $1\leq x<2$.


Optimal constant $C$ for a particular pair of distances

$C(r) = r / \lfloor r \rfloor$, where $r = d_2/d_1$ is the ratio of the two distances

As Alexandre has already written in his solution, the global maximum for $C$ is $2$, and it is achieved, when $r$ is just slightly below $2$.

Optimal Racing Strategy

To illustrate how the optimal racing strategy for the runner who runs the longer distance looks like, let's walk through an example.

Johnny runs 10 km in 1 hour. Superman wants to run a marathon in the shortest possible time without exceeding Johnny's average speed on any 10-km-segment. So we have $d_1 = 10000$, $d_2 = 42195$, and $r = 4.2195$.

Superman divides the marathon into k = $\lfloor r \rfloor + 1= 5$ equal segments by placing $\lfloor r \rfloor$ stops at the positions $d_2 * i/k$ for $i=1,...,\lfloor r \rfloor$. In our example, each of the 5 segments has a length of 8439 metres.

Superman then runs each segment at the speed of light and rests for exactly $t_1$ = 1 hour at each stop. Since any interval of length $d_1$ contains exactly one such stop, the time for any such interval is always slightly above $t_1$, as demanded by the rules. Superman's total time for $d_2$ is just an $\epsilon$ above $\lfloor r \rfloor * t_1$ = 4 hours, the total time he spent resting at the stops. His average speed is $v_2 = d_2 / (t_1 * \lfloor r \rfloor) = r * d_1 / (\lfloor r \rfloor * t_1) = r / \lfloor r \rfloor * v_1$.

The $C$ he achieves with this strategy is therefore $r / \lfloor r \rfloor$ = 4.2195 / 4 = 1.054875.

Why is this optimal?

It remains to show that Superman's strategy is optimal. To see this, assume that he finished in less than $\lfloor r \rfloor * t_1$ = 4 hours. Divide his race into $\lfloor r \rfloor = 4$ equal time slices and look at the distance he covered in each time slice. At least one of these distances will be longer than $d_1$, and each time slice is shorter than $t_1$, which means that he violated the speed limit in that time slice.

  • $\begingroup$ +1 very nice explanation - thanks Mark! $\endgroup$ – Dominic van der Zypen Dec 7 '18 at 13:58

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.