Bicycle Route Optimization Puzzle

I tried to make some expressions about where each person stops the bike, but I couldn't solve it :( There are three people who would like to cross the road.

It takes $a$ minutes for the first person to cross the road by walking.

It takes $b$ minutes for the second person to do so.

It takes $c$ minutes for the third person to do so.

They also have one bike - all three of them can cross the road in $k$ minutes - where $k<a,b,c$.

However, only one person at a time can ride the bike.

Now they want to cross the road as fast as possible. What is the shortest time possible for all three of them to arrive at the end of the road?

The below solutions have some cases where people go outside the road - also possibly implying negative time.

• Unless I am missing something, can't you just give the bike to the slowest guy for the whole trip?
– Ovi
Jun 1 '16 at 6:07
• @Ovi: It depends: perhaps you can leave the bike in the middle of the road so the two slowest can share it, or perhaps the faster walker is so fast it is better for the bike to cross the road three times Jun 1 '16 at 6:11
• did you post a duplidate of this to puzzling? may be they are used to solve these problems and more interact with this Jun 9 '16 at 17:43
• Can you tell us the source of this problem? Jun 10 '16 at 10:23
• I think to "cross the road" is the wrong phrase. I think it means to go from one side to the other side. Jun 10 '16 at 11:12

First, it will be useful to notice two principles

1. All walkers, no matter how many they are, have to get to the end of the road at the same time, always. If some walker got before another, it could have given some of her "bicycle time" to the walker that arrived the last to decrease the total time.
2. It doesn't make sense for any walker at any time to go backwards to give the bicycle to other walker. Going back is less efficient than just letting the bicycle in the road and keep walking.

The total crossing time is determined by the proportion of walking to riding time, that should be adjusted so that all walkers get to the end of the road at the same moment.

If you let me, I will use speeds rather than times. We'll call the speeds of the walkers $v_1,v_2,v_3$ and the one of the bicycle $V$. Also, lets assume, without loss of generality, that $$v_1<v_2<v_3<V$$ The simplest procedure the walkers could choose to adjust their riding to walking ratio is the following. The slowest walker takes the bicycle up to a distance $d_{c1}$ (the $c$ is for "cut") then leaves it and walks through the end $d$. The middle walker walks until $d_{c1}$ then takes the bicycle up to $d_{c2}$ and walks to the end. Finally, the fastest walker walks to $d_{c2}$ and takes the bicycle to the end. We'll call the total crossing times for the three walkers $t_1,t_2,t_3$. They have the following expressions $$t_1=\frac{d_{c1}}{V}+\frac{d-d_{c1}}{v_1}$$ $$t_2=\frac{d_{c1}}{v_1}+\frac{d_{c2}-d_{c1}}{V}+\frac{d-d_{c2}}{v_2}$$ $$t_3=\frac{d_{c2}}{v_3}+\frac{d-d_{c2}}{v_2}$$ Now, our first principle sets the constraints $t_1=t_2=t_3=t_T$ (total time). With this we have three linear equations to determine three unknowns, $t_T,d_{c1}$ and $d_{c2}$. Actually I just put the equations in Mathematica and obtained

$$t=\frac{d}{V}\frac{2V^3+v_1v_2v_3-V^2(v_1+v_2+v_3)}{3 v_1v_2v_3+V^2(v_1+v_2+v_3)-2V(v_1v_2+v_1v_3+v_2v_3)}$$ $$d_{c1}=d\frac{-2Vv_1v_3+v_1v_2v_3+V^2(-v_1+v_2+v_3)}{3 v_1v_2v_3+V^2(v_1+v_2+v_3)-2V(v_1v_2+v_1v_3+v_2v_3)}$$ $$d_{c2}=2d\frac{(V-v_1)(V-v2)v_3}{3 v_1v_2v_3+V^2(v_1+v_2+v_3)-2V(v_1v_2+v_1v_3+v_2v_3)}$$

The most interesting point is that the total time is symmetric to permutations of $v_1,v_2,v_3$, i.e. we could have made the fastest or the middle walker to take the bicycle first, it doesn't matter, as long as the bicycle times proportions are kept. Besides the grueling algebra, that could be perhaps simplified with some tricks, I think this problem would be easy to generalize for more walkers.

• There are some cases where $d_{c2} > d$. We cannot go outside the road. Jun 10 '16 at 8:40
• You assume that a walker uses a bicycle only once Why can you do this? Jun 10 '16 at 9:49
• How do you proof your two assumptions? At least your first assumption is wrong. Jun 10 '16 at 9:54
• Your assumption 2 is disproved by the following example: Assume $$0\approx v_1= v_2\ll v_3 \approx V$$if $v1$ and $v2$ are very small compared to $v_3$ than the best strategy may be: person 2 takes the bicycle and both person 1 and person 2 move almost to the end of the road. person 1 then takes the bicycle and moves back to the start until he meets person 3. Both person 1 and person 2 move to the end. When they arrive there person 2 also arrives. Jun 10 '16 at 12:17
• To see that your first assumption is wrong assume $$v_1=v_2 \ll v_3\approx V$$If the values are choosen appropriate the best strategy is that person 1 moves to the target without using the bike and that person 2 and person 3 both use the bike to move to the end of the road Person 1 is so fast as the bike so he will arrive before person 2 and person 3 because both of them have an average velocity that is lower than the velocity of the bicycle. Jun 10 '16 at 12:23

Here is an example: suppose $k=26, a=52, b=65, c=78$ minutes (a wide road).

Then I suspect an optimal choice is for the third person to ride for $14$ minutes, getting $\frac{14}{26}$ of the way across, leaves the bike there, and walks the rest of the time, taking $\frac{26-14}{26}\times 78 = 36$ extra minutes, making a total of $14+36=50$ minutes.

At the same starting time, the first person walks to where the bicycle will be left by the third, taking $\frac{14}{26}\times 52 = 28$ minutes to get there, then rides the bike for $2$ minutes, so is now $\frac{14}{26} + \frac{2}{26} = \frac{16}{26}$ of the way across, leaves the bike, and finally walks across the rest of the road, taking $\frac{26-16}{26}\times 52 = 20$ extra minutes, making a total of $28+2+20 = 50$ minutes again.

At the same starting time, the second person walks to where the bicycle will be left by the first, taking $\frac{16}{26}\times 65 = 40$ minutes to get there, then rides the bike for $10$ minutes, so is now $\frac{16}{26} + \frac{10}{26}=1$ i.e. the whole way across, making a total of $40+10 = 50$ minutes again.

So in this example it is possible for all three people and the bike to cross in less time than the fastest person walking, and faster than the bike going there and back.

Generalising this, but with the same bike order of slowest, then fastest, then middle-speed riding, I suspect that the fastest time comes from:

• first person riding for $k\frac{ {{k}^{2}}-2 a k-b c+a c+a b }{3 {{k}^{2}}-2 c k-2 b k-2 a k+b c+a c+a b}$ minutes and walking for $a\frac{2k^2-2ck-2bk+2bc}{3 {{k}^{2}}-2 c k-2 b k-2 a k+b c+a c+a b}$ minutes

• second person riding for $k\frac{ {{k}^{2}}-2 b k-c a+b a+bc }{3 {{k}^{2}}-2 a k-2 c k-2 b k+ca+ba+bc}$ minutes and walking for $b\frac{2k^2-2ak-2ck+2ca}{3 {{k}^{2}}-2 a k-2 c k-2 b k+ca+ba+bc}$ minutes

• third person riding for $k\frac{ {{k}^{2}}-2 c k-ab+cb+ca }{3 {{k}^{2}}-2 b k-2 a k-2 c k+ab+cb+ca}$ minutes and walking for $c\frac{2k^2-2bk-2ak+2ab}{3 {{k}^{2}}-2 b k-2 a k-2 c k+ab+cb+ca}$ minutes

so with total crossing time of $\dfrac{k^3-bck-ack-abk+2abc}{3 {{k}^{2}}-2 c k-2 b k-2 a k+b c+a c+a b}$ for each person.

This does not work when it gives a negative riding time for the fastest walker, suggesting riding in the opposite direction, as that individual still needs a non-negative riding time.

• You make a lot of assumptions you did not prove. I think it makes no sense that the fastest person picks up the bicycle that the slowest person has left. I think it is better he does not but leaves it for the slower person. Jun 10 '16 at 10:22
• @miracle173: In the example I started with of $k=26, a=52, b=65, c=78$, my method takes $50$ minutes while yours would take at least $52$ minutes as the fastest person has to walk all the way. Jun 10 '16 at 14:32
• I did not do the calculation I made the (wrong) assumption that it is better that the slower of too people picks up the bicycle as soon as possible.. Jun 11 '16 at 5:18

WARNING

The formula given for Case$1$ doesn't necessarily give the optimal time, trial and error can throw up better answers (see comments below the answer), but the formula for Case $2$ should be ok, as all reach the end simultaneously.

There are two assumptions I make at start:

(i) the bike is faster than each of the walkers (reasonable !)

(ii) zero time is wasted in switching from bike to walk or vice versa (unreasonable but customary !)

WLOG, I take time to bike entire distance as $1$, and that of the walkers as $a,b,c,\;\; a < b < c$

[ The cases where two or three have the same walking speed are progressively simpler cases ]

First consider the two slowest walkers.

Let (say) the faster one start with the bike, leave it at fraction $f$ of the distance, and walk the rest of the way, whereas the other walker starts by walking, and rides the remaining distance on reaching the bike.

Let $t$ be the time needed for both of them to simultaneously reach the end, then

$f + (1-f)b = (1-f) + f*c = t\;\; \Rightarrow f = \dfrac{b-1}{b+c-2}$

and $\;t = \dfrac{bc-1}{b+c-2}$

Two cases can now arise:

Case $1:\;t > a$

Example:$\; a = 1.5, b = 2, c= 20 \to t= 1.95$

Decision rule: Let $a$ walk the whole distance. Optimal group reach time $= 1.95$

Case $2:\;t \le a$

Example:$\; a = 1.5, b = 1.6, c= 1.7 \to t= 1.323$ (considering only $b$ and $c$)

Decision rule: All three should share the bike for appropriate fractions of the distance and arrive simultaneously.

Appropriate fractions

Let $f_1,f_2,f_3$ be the fractions of full distance the bike is used by $a,b,c$
and the time taken for them to reach simultaneously be $t$

$f_1 + (1-f_1)a = t \to f_1 = \dfrac{a-t}{a-1}$
$f_2 + (1-f_2)b = t \to f_2 = \dfrac{b-t}{b-1}$
$f_3 + (1-f_3)c = t \to f_3 = \dfrac{c-t}{c-1}$

Now $f_1+f_2+f_3 = 1$, which yields:

$t = \dfrac{(2 a b c - a b - a c - b c + 1)}{(a b + a c + b c - 2 a - 2 b - 2 c + 3 )}$

Using the above decision rule brings down the optimal time from $1.5$ (due to laggard $a$ to $\approx 1.3925$

• Okay. Take the case where the three people need 10,5,2 minutes to cross the road. See what happens by plugging the numbers yourself. Jun 12 '16 at 11:34
• Considering 10 and 5, t = 3.769 >2, so it is case 1 and the optimal time is 3.769. What's wrong ? Jun 12 '16 at 12:28
• I heard that faster solution exists Jun 12 '16 at 12:30
• I can't see how. We have fully utilized the bike for the two slowest walkers. Jun 12 '16 at 12:34
• How about this - maybe the slowest walker rides the bike a bit long - then the fastest walker take the bike back to the second fastest walker - then they go to the end. Jun 12 '16 at 13:57