4
$\begingroup$

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:

At the beginning

$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?

$\endgroup$
2
  • 4
    $\begingroup$ Chvatal, "On the Bicycle Problem" (1983) $\endgroup$
    – RobPratt
    Apr 17 '20 at 18:16
  • 2
    $\begingroup$ @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. $\endgroup$
    – Eric
    Apr 18 '20 at 5:07
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – Eric
    Apr 19 '20 at 9:25
  • $\begingroup$ It merely makes the schedule more complicated. $\endgroup$ Apr 19 '20 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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