# The motorcyclist's challenge

Three passengers $$1,2,3$$ starts out moving at constant speeds from $$A$$ to $$B$$. At the same time, a motorcyclist $$M$$ starts out from $$B$$ towards $$A$$ to pick the passengers up. As illustrated below:

$$M$$, however, can carry at most one passenger on board. He can drop his passenger off at anytime. When off the motorcycle, passengers just keep moving forward to $$B$$ at their respective speeds. $$M$$ can drive forward or backward, any way he wishes, at any speed not exceeding his top speed. Passengers will get on or off board at $$M$$'s bidding, and let $$M$$ drive them forward or backward with no complaint. We assume it takes no time to get on and off the motorcycle, or for $$M$$ to switch lanes to pick up different passengers.

$$M$$'s goal, or challenge, is to make all passengers arrive at $$B$$ simultaneously.

Now assume speeds for $$1$$ and $$2$$ are $$60$$ and $$90$$ respectively, and a top speed of $$100$$ for $$M$$.

Question: What is $$3$$'s speed range, if $$M$$ is able to accomplish his challenge?

Hint:

Distance between $$A$$ and $$B$$ is irrelevant.

Here's a more involved one if you solved the above:

Instead of 3 passengers we now have 4, where $$1,2,3$$ have speeds $$60,90,30$$ respectively. Top speed for $$M$$ still is $$100$$. What is $$4$$'s speed range, if $$M$$ is able to accomplish his challenge?

and

In general, What relationship must the speeds for 3 passengers $$s_1,s_2,s_3$$ satisfy, given $$s_m=100$$ and $$M$$ is able to fulfill his challenge? What relationships must the speeds for 4 passengers satisfy?

and

If there are many passengers and the speed of $$M$$ is sufficiently large relative to the speeds of passengers. What is the most efficient way (aka requiring the least amount of time) for $$M$$ to accomplish his challenge?

• Chvatal, "On the Bicycle Problem" (1983) Apr 17 '20 at 18:16
• @RobPratt Thanks. Though your reference is interesting for its own sake, I think it is a totally different problem in nature. And unlike your reference problem, my problem seems not amenable to algorithmic treatment, i.e. there exists no general algorithm that can decide whether a given speed vector $(s_1,s_2,...,s_n,s_M)$ is feasible for $M$, or if so, what schedule $M$ should make. Analysis can only be made case by case, conditioning on the number of passengers.
– Eric
Apr 18 '20 at 5:07

Normalize the problem so that the motorcycle starts at 0 with max speed 1 and the passengers start at 1. Answer to part 1: If passenger 3 is slower than passenger 1,

Drive to passenger 2 and pick him up at $$10/19$$. (Time: $$10/19$$)
Keep driving up and drop him off at $$15/19$$. (Time: $$15/19$$)
Drive to $$5/6$$. (Time: $$5/6$$)
Drive back to 0, picking up passenger 3 whenever you meet him.
The first two passengers reach 0 at time $$5/3$$, and the third reaches 0 iff he is at $$5/6$$ on or before time $$5/6$$, which occurs if his speed it at least $$1/5$$.

If passenger 3 is faster than passenger 1, denote the time it takes him to walk from A to B by T.

Drive to passenger 2 and pick him up at $$10/19$$. (Time: $$10/19$$)
Keep driving up and drop him off at $$9T/19$$. (Time: $$9T/19$$)
Drive to $$T/2$$. (Time: $$T/2$$)
Drive back to 0, picking up passenger 1 whenever you meet him.
The last two passengers reach 0 at time T, and the first reaches 0 iff he reaches $$T/2$$ on or before time $$T/2$$. Since passenger 1 has speed $$3/5$$, T must be at least $$5/4$$, forcing passenger 3's speed to be at most $$4/5$$.

In conclusion, passenger 3's range is

$$1/5$$ to $$4/5$$, inclusive.

Generalizing the above approach for problem 3, let the three passengers have speeds a, b, and c, in descending order.

The fastest passenger is picked up at 1/(1+a) and dropped off at (a/b)/(1+a).
We continue driving to 1/(2b). This is only possible if 1/(2b) is at least (a/b)/(1+a), which is true whenever a is at most 1.
We pick up the slowest passenger on the way back, and everyone arrives at time 1/b iff the slowest passenger has made it to 1/(2b) at time 1/(2b): This is true whenever c is at least 2b-1.
In conclusion, the fastest passenger is not faster than the motorcycle, and the middle passenger is not faster than the average of the slowest passenger and the motorcycle.

Regarding @Eric's comment, I don't believe we can do any better, and here's why:

In order to have time to delay the middle passenger, we need to bring the fastest passenger as far back as we can.
This would be to some point 1/(2b) - $$\epsilon$$, since we have to get back to the middle passenger before he reaches 0 at time 1/b.
Since the farthest we move is still 1/(2b) at time 1/(2b), the slowest passenger's bounds are the same.
The fastest passenger will now reach 0 at time (1+1/a)/(2b), and for this to be later than 1/b (so that we can delay the middle passenger) we must still have a at most 1, and the fastest passenger's bounds are the same.

• If $v_m\gt v_1\gt v_2\gt v_3$ and $2v_2=v_3+v_m+\epsilon$, what about $M$ driving both $v_1$ and $v_2$ backward some distance before picking up passenger $3$?
– Eric
Apr 19 '20 at 9:25
• It merely makes the schedule more complicated. Apr 19 '20 at 13:20