The motorcyclist's challenge

Question

n walkers ${A}_{i}$ start out from X to Y simultaneously with speeds ${a}_{i}$, $i=1,2,...,n$. ${a}_{i}\neq {a}_{j}$ if $i\neq j$. At the same time, a motorcyclist M with speed $m=1$ starts out from Y to carry them (as shown in the illustration attached). The motorcyclist can pick up any person he meets. He can carry at most one person. But he's free to drop off the person he carries at any time. Walkers just walk straight forwards (from X to Y), while motorcyclist is free to drive either forwards or backwards.

The motorcylist's goal is to find a plan under which all the walkers arrive at Y simultaneously, if such a plan exists. We call such a plan a feasible plan.

Define the configuration of the problem to be the n-tuple $({a}_{1},{a}_{2},...,{a}_{n})\in {\mathbb{R}}_{++}^{n}$.

Define ${B}^{n}\subseteq{\mathbb{R}}_{++}^{n}$ to be the set of all feasible configurations (i.e., configurations for which a feasible plan exists).

Trivially, we know that ${B}^{1}={\mathbb{R}}_{++}$ and ${B}^{2}={\mathbb{R}}_{++}^{2}$. Also it's easy to see that ${B}^{n}\subseteq {(0,1)}^{n}$ for $n>2$. However, it is nontrivial to find ${B}^{n}$ for $n>2$. Without loss of generality, assuming ${a}_{1}<{a}_{2}<...<{a}_{n}$, I find that ${B}^{3}=\{({a}_{1},{a}_{2},{a}_{3})| 2{a}_{2}\leq{a}_{1}+1,\ {a}_{3}<1 \}$, which is neat!

---

When I tried to figure out ${B}^{4}$, however, I found it to be significantly harder than ${B}^{3}$. So I have two related questions here:

1.How should we tackle ${B}^{n}$? Is there some systematic method we can use to characterize ${B}^{n}$ for successive n's?

2.If not, can we speculate what ${B}^{n}$ will look like, for example by giving some upper and lower bound on it which we are able to characterize?

---

EDIT: $n=4$ is EXHAUSTING, and honestly I have no idea where to start. Maybe it's just impractical to find ${B}^{n}$ for $n>3$. An interesting way to simplify the model is to assume that M can teleport himself anywhere he wants (as long as the motorcycle is not loaded). This assumption may allow a cleaner analysis and nicer answer.

Answer 1

Well, this is not really an answer. It is motivated by fedja's comment. In the original problem we do allow motorcyclist (M) to drive walkers backward. If not, I think I can say something more:

If driving walkers backward is not allowed, the best M can do is trying to successively drive slower walkers forward enough to correct positions before the fastest walker reach Y. Conceivably in a feasible configuration then, if he is visionary enough, M can figure out a plan in which he never goes forward unloaded (in this plan, when M placed someone in correct position, he immediately turns back to pick another walker). If this is true, then half of time M is empty (going backward), and half of time it's loaded (going forward).

Let $T$ be the total time lapse of this plan, $L$ be the distance between XY, ${t}_{i}$ be the time on the motorcycle for walker $i$, then we have:

$\sum{t}_{i}=T/2$

${t}_{i}+(T-{t}_{i}){a}_{i}=L\ $ for $i=1,2,...,n$

which is n+1 equations for n+1 unknowns. What is perhaps a little surprising about the plan is that the total time $T$ doesn't depend on whom M decides to pick first, and whom to pick later. Maybe this is not very relevant to my original questions, but I can't help remark on it.

Answer 2

[[Please see SECOND EDIT at the bottom before bothering to read this]]

I'm not sure that $B^3=\{(a_1,a_2,a_3)|2a_2≤a_1+1, a_3<1\}$ is the right answer. I find that the feasible set for $n=3$ includes a region defined by

$${3a_2a_3 + a_2 - a_3 -1 \over 3 + a_2 + a_3 - a_2a_3} < a_1$$

(following the convention $a_1 < a_2 < a_3$). The denominator on the left hand side is always positive, but the numerator is negative when $a_2=1/2$, which means there are feasible configurations with $2a_2 > a_1+1$ --- just pick a value of $a_2$ slightly larger than $1/2$ that keeps the left hand side negative and then pick $a_1$ smaller than $2a_2-1$.

Note, I'm not saying that this inequality defines the feasible set, merely that it specifies a portion of it.

Here's my reasoning. The motorcyclist will first encounter walker 3, and can transport him back to walker 2. He can then effectively "bind" those two walkers together, in a way I'll describe below, and slow them down to a speed arbitrarily close to the left-hand side above, while walker 1 saunters by. When walker 1 has a sufficient lead, the motorcyclist can "release" walker 2 and either "hold" walker 3 in place or transport him some distance back before releasing him -- all timed so that walkers 2 and 3 catch up with 1 at the finish line.

Here's what I mean by "binding" walkers 2 and 3 together. For convenience, let's use a number line that has walker 3 (being carried left on the motorcycle) meet walker 2 at $x=0$. For a short time $\delta$, let walker 3 continue heading left on the motorcycle, so that he's now at $x_3 = -\delta$ while walker 2 is at $x_2 = \delta a_2$. Now drop off walker 3 and zip off to catch walker 2. This will take time $\Delta = \delta(1+a_2)/(1-a_2)$, at which time walker 3 is at $\Delta a_3-\delta$ and walker 2 is at $(\Delta + \delta)a_2$. If the mortorcyclist now picks up walker 2 and heads back to the left, they meet walker 3 after time $$\Delta' = {(\Delta + \delta)a_2 - (\Delta a_3 - \delta) \over 1+a_3}$$ at which point they are at $$x = \Delta a_3 - \delta + \Delta'a_3$$ and the process can repeat (i.e., take walker 3 back for time $\delta$, etc.). By taking $\delta$ small, the two walkers can be kept close together, and their average speed over a complete cycle is

$${\Delta a_3 - \delta + \Delta'a_3 \over \delta + \Delta + \Delta'} = {3a_2a_3 + a_2 - a_3 -1 \over 3 + a_2 + a_3 - a_2a_3}$$

(Caveat: I did the algebra here three times by hand, and got the same answer on the last two tries. You can judge for yourself the probability of the result being correct.)

It's worth noting why the inequality doesn't define the feasible set. It's because even if the inequality is (slightly) violated, there might be a $\delta$ for which the motorcyclist encounters walker 1 while he's transporting walker 3 to the left. If that happens, he can immediately drop off walker 3, pick up walker 1, and zip him some distance to the right, and then come back for walkers 2 and/or 3 and position them so that everyone arrives simultaneously at the finish line.

EDIT: Forget a fair amount of what I said above. I forgot to consider that walker 1 may have a considerable distance to make up while walkers 2 and 3 are bound together. The safest thing to say is that the feasible set includes a region defined by

$${3a_2a_3 + a_2 - a_3 -1 \over 3 + a_2 + a_3 - a_2a_3} < 0$$

which describes a setting where the bound pair move to the left while walker 1 proceeds to the right.

SECOND EDIT: I should have tried doing the algebra one more time by hand before posting this. The correct average speed (I think) is

$${\Delta a_3 - \delta + \Delta'a_3 \over \delta + \Delta + \Delta'} = {3a_2a_3 + a_2 + a_3 -1 \over 3 + a_2 + a_3 - a_2a_3}$$

Note the $+a_3$ is the numerator, which corrects the $-a_3$ I originally obtained. This pretty well invalidates everything I had hoped to show.