0
$\begingroup$

Puzzle

Two identical runners are supposed to transport a message from A to B across a distance $d$ in minimal time $t_{min}$.

Preliminaries

The capacity of the two runners is described by

  • their maximal speed $v_{max}$

  • a function $T(d)$ giving the minimal time it takes them to run distance $d$.

For the sake of explicitness, let's consider two such functions:

$$T_1(d) = \alpha_1 (e^{\lambda d} - 1)$$

$$T_2(d) = \alpha_2\ d^{\epsilon}$$

with $\alpha_1, \alpha_2, \lambda > 0$, $\epsilon > 1$, indicating that the runners get slower in the average for longer distances.

For any given distance $d$ there are many "speed profiles"

$$v(t): [0,T(d)]\mapsto [0,v_{max}],$$

with $v(t) \leq v_{max}$ for all $t \in [0,T(d)]$, which allow the runner to cover distance $d$ in minimal time $T(d)$:

$$\int_0^{T(d)}v(t)dt = d$$

But not each such $v(t)$ is allowed. $v(t)$ also has to fulfill the conditions

$$\int_{t_1}^{t_2}v(t)dt \leq T^{-1}(t_2 - t_1)$$

for all $0 \leq t_1 < t_2 < T(d)$, because otherwise the distance covered between $t_1$ and $t_2$ would be greater than allowed by $T^{-1}(t)$.

Furthermore, $v(t)$ is supposed to be piecewise smooth.

Solutions

When both runners start at $A$ at $t=0$, there is obviously no way to arrive at $B$ earlier than $T(d)$.

If one of the runners waits halfway along the distance, the runners can transport the message in time $t = 2\ T(d/2) < T(d) $ (principle of relais stations, e.g. in the time of diligences). For $d=1$ and $T(d) = d^2$ we get $t = 0.5$ opposed to $T(1) = 1$.

But now consider the case that the first runner starts at A with the message, the second runner is supposed to run from B to A, not starting earlier than the first runner, i.e. running to meet the first runner somewhere between A and B, taking the message and returning to B.

Questions

  1. Which speed profiles $v_1(t), v_2(t)$ do the two runners have to choose, and when does the second runner have to start, to minimize the overall time it takes the second runner to return to B with the message?

  2. What's the value of $t_{min}/T(d)\leq 1$ as a function of the parameters $\alpha, \lambda, \epsilon$ above?

  3. How to solve this problem systematically, not by guessing?

  4. How to prove the correctness of the result?

Guess of an answer to question 2

Let the distance between A and B be $d=1$. Let the first runner start at $t_0=0$ with constant speed $v_1 = 0.75 / T(0.75)$. He will arrive at $0.75$ at time $t_1 = T(0.75)$. Let the second runner start at B with constant speed $v_2 = 0.5 / T(0.5)$ such that he arrives at $0.75$ at time $t_1$ and then returns to B. The overall time $t$ it takes for the message to arrive at B is

$$t = t_1 + 0.25/v_2 = T(0.75) + 0.25/(0.5 / T( 0.5)) = T(0.75) + 0.5 T(0.5) < T(1)$$

For $T(d) = d^2$, we get $t = 0.75^2 + 0.5^3 = 0.6875$, which is a significant speed-up, but probably not the maximal one.

$\endgroup$
1
$\begingroup$

When $T_1$ and $T_2$ are convex, the optimum is the minimum of a convex function:

$$t_{\mathrm{min}}=\min_{0\leq x\leq d}(\max\{T_1(x),v_{\mathrm{max}}x\} + \max\{T_2(d-x),v_{\mathrm{max}}(d-x)\}).$$

Correctness follows from the fact that $v(x)=\max\{T_1(x),xv_{\mathrm{max}}\}$ is a valid "distance profile" for the first runner: for $0\leq x\leq x'$ it satisfies $v(x')-v(x)\geq \max\{T_1(x'-x), v_{\mathrm{max}}(x'-x)\}$, and similarly for the second runner. This is an exercise in using convexity.

Minimizing a convex function is generally tractable. You might even get an analytic solution in some cases, by the usual method of finding where the derivative (which is non-decreasing) goes from negative to positive.


I suspect non-convex $T$ will be awkward in general. If $T_1$ and $T_2$ already satisfy $T_i(x)\geq v_{\mathrm{max}} x$ and superadditivity ($T_i(x+y)\geq T_i(x)+T_i(y)$) then the $T_i$ already define valid distance profiles and you merely need to maximize $T_1(x)+T_2(d-x)$ somehow. Depending on the application it might be worth looking at a discrete model, which would allow efficiently computing minima.

$\endgroup$

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.