Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?
alt text


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.

share|improve this question
2  
I do not see the illustration, only some Chinese characters and reference to baidu. –  Fedor Petrov Aug 9 '11 at 10:11
    
@Fedor: The illustration can be seen now. –  user16033 Aug 9 '11 at 12:44
    
For n=3, there are some feasible sets with the fastest walker having velocity equal to 1 (and with enough distance, the slowest walker not walking at all) . I'm assuming multiple lanes and instantaneous reversals and transitions. Also, it might be useful to consider the feasibility of just doing the swapping of the kth fastest and kth slowest walkers for enough k. Gerhard "Ask Me About System Design" Paseman, 2011.08.09 –  Gerhard Paseman Aug 9 '11 at 16:49
1  
@fedja, in order for the feasible set for $n=2$ to be the entire first quadrant, the motorcyclist must be able to drive the faster walker backward (if that walker's pace is greater than or equal to 1). –  Barry Cipra Aug 10 '11 at 4:11
1  
Is the motorcyclist allowed to drop a walker to the left of $X$? –  Brendan McKay Sep 8 '11 at 15:10
show 3 more comments

2 Answers

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.

share|improve this answer
add comment

[[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.

share|improve this answer
    
@Barry: Your idea is correct. Actually I considered this approach, too. The only difference is that I also took the distance $L$ into my calculation. $L$ cancels out in the end, as one would expect, leaving me with $(3{a}_{2}{a}_{3}+{a}_{2}+{a}_{3}-1)/(3+{a}_{2}+{a}_{3}-{a}_{2}{a}_{3})<{a}_{1}$‌​, which defines a subset of my characterization of ${B}^{3}$. –  user16033 Aug 10 '11 at 6:19
    
@unknown, your comment came in while I was posting my second edit. The real difference between us is that you did the algebra correctly. I finally realized something was amiss in my formula for the average speed when it occurred to me that it implied a negative average speed for $a_2 = 1/2$ even when $a_3$ is close to 1, which is patent nonsense. –  Barry Cipra Aug 10 '11 at 6:28
    
and the $<0$ part is too stringent. the exact boundary is $<{a}_{1}$. As long as $<{a}_{1}$ is satisfied, ${a}_{1}$ can always catch up. This inequality defines a subset of B3={(a1,a2,a3)|2a2≤a1+1,a3<1}. So that characterization still holds. –  user16033 Aug 10 '11 at 6:41
add comment

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.