0

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.

Hans-Peter Stricker
  • 18,159

1 Answers1

1

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.

Dap
  • 25,286