Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

n walkers ${A}_{i}$ ($i=1,2,...,n$) start out from X to Y simultaneously with constant speeds ${a}_{1}<{a}_{2}<...<{a}_{n}$. At the same time, motorcyclist M with speed $m=1$ starts out from Y to carry them, as shown below:

Motorcyclist and 3 walkers

The motorcyclist can choose to pick up a walker upon meeting. He can carry at most one person, but is free to drop off the person he carries at any time. Left to themselves, walkers walk straight forward (from X to Y) with the given speeds $a_i$, while motorcyclist is free to drive either forwards or backwards, loaded or unloaded.

The motorcylist's objective (challenge!) 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, and call the $({a}_{1},{a}_{2},...,{a}_{n})$ for which a feasible plan exists a feasible configuration. For given n, define the set of all feasible configurations as feasible set ${B}_{n}$.

The question:What is the feasible set ${B}_{n}$ like? Or at least, what is ${B}_{4}$ like?

n=2 is trivial because ${B}_{2}={\mathbb{R}}_{++}^{2}$. I worked out the n=3 case, for which ${B}^{3}=\{({a}_{1},{a}_{2},{a}_{3})| 2{a}_{2}\leq{a}_{1}+1,\ {a}_{3}<1 \}$. Despite the simple final answer, however, there're a lot of subtleties, nuances and discussions one need to fill in the process, which really makes me doubt if one can really characterize ${B}_{n}$ for even moderately large n.


Alternatively, for given n, one may try to look for a kind of dominant plan (or a rule,a set of instructions for what to do, if you wish) for the motorcyclist, in the sense that if this plan doesn't work, no other plan does. If we succeed in finding one, given any configuration, we can simply input it to a computer program that simulates the whole process using the plan and see the outcome. In short, we make the question "given a configuration, decide if it's feasible" a decidable one. For n=3, one can show the following is a dominant strategy:

1) Upon meeting ${A}_{3}$, drive him back and drop him at position x before meeting ${A}_{1}$, where x is chosen such that 2) is satisfied:

2) Pick up ${A}_{1}$ and carry him forward to meet ${A}_{2}$ at some position y. x in 1) is chosen such that ${A}_{3}$ now just arrive at y, too. A configuration will be feasible iff y$\leq$the destination Y.

(Necessarily, this gives the ${B}^{3}$ I described earlier, too)


I actually posted this on MO about half a year ago and no one's given a define answer: http://mathoverflow.net/questions/72449/the-motorcyclists-challenge. I also wonder whether anything could be said about ${B}_{n}$ for large n? Speculations are appreciated, too.

share|improve this question

1 Answer 1

Consider an easier version of the problem, in which walkers are in a hurry heading for Y, so they will not allow M to drive them backward. Clearly, if $({a}_{1},{a}_{2},...,{a}_{n})$ is feasible, then $({b}_{1},{b}_{2},...,{b}_{n})\leq({a}_{1},{a}_{2},...,{a}_{n})$ will also be feasible. So we only need to consider the "boundaries".

Definition: $({a}_{1},{a}_{2},...,{a}_{n})$ is a boundary configuration (BC) if the only feasible $({b}_{1},{b}_{2},...,{b}_{n})\geq({a}_{1},{a}_{2},...,{a}_{n})$ is $({a}_{1},{a}_{2},...,{a}_{n})$ itself.

Solution depends essentially on the following claim:

Claim: In a feasible plan for BC, M can never drive forward with an empty backseat.

Why? Conceivably in this case, the best M can do is trying to successively drive slower walkers forward enough to correct positions. When a walker is dropped, M immediately turns back to pick another one, so that all the other walkers reach Y at the same time just as M arrives with his last carry.(Although I think it is probably true, this is no proof for the claim. Further evidence for or against it is appreciated)

The crucial observation is that if the claim is true, then for exactly half of the time M is unloaded and going backward, and is loaded and going forward for the rest half. (Because he starts from Y and finally returns to Y, with zero displacement)

Note that distance between X and Y is irrelevant for our purpose. For convenience, let it be $1$. Let $T$ be the total time lapse, ${t}_{i}$ be length of time that walker $i$ is on the motorcycle. By the observation made above we have:

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

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

Which gives:

$T=\sum_i1/(1-a_i)/(1/2+\sum_i\frac{a_i}{1-a_i})$

$t_i=(1-{a}_{i}T)/(1-a_i)$

Notice that interestingly, total time lapse is independent of M's decision about picking order. To guarantee that $({a}_{1},{a}_{2},...,{a}_{n})$ is indeed feasible, we need $t_i\geq 0$ for all $i$, which means $a_i\leq 1/T$, which means $a_n=1/T$ (since we are at the boundary, and $a_n$ is the largest). Hence $a_n\leq 1/\sum_i1/(1-a_i)/(1/2+\sum_i\frac{a_i}{1-a_i})$, which characterizes the $B_n$ we desire for $n\geq 2$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.