7

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?

Please note, that these people cannot go outside the road.

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

rkm0959
  • 3,437

3 Answers3

2

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.

Way Too Simple
  • 784
  • 2
    There are some cases where $d_{c2} > d$. We cannot go outside the road. – rkm0959 Jun 10 '16 at 08:40
  • You assume that a walker uses a bicycle only once Why can you do this? – miracle173 Jun 10 '16 at 09:49
  • How do you proof your two assumptions? At least your first assumption is wrong. – miracle173 Jun 10 '16 at 09:54
  • Without proofs of all the assumptions you made that is not an answer to the problem. – miracle173 Jun 10 '16 at 10:00
  • To see that your first assumption is wrong assume $v_3 \approx V$ – miracle173 Jun 10 '16 at 10:04
  • 2
    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. – miracle173 Jun 10 '16 at 12:17
  • 2
    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. – miracle173 Jun 10 '16 at 12:23
  • @miracle173 you are totally right, my thinking was grossly simplifying. A principle that should be met, at least, is that the bicycle (with a person riding it, of course) should arrive the last. Do you agree with me? I'm working from this, but not advancing too much yet. – Way Too Simple Jun 10 '16 at 16:27
  • @moonshine: I don't know, so I cannot agree. If you provide a proof for this assumption I can check it and if it is correct then I can agree with you. – miracle173 Jun 11 '16 at 05:16
  • @miracle173: Re your comment as to why the bike is used only once by each person, it could be broken up into more trips, but it only complicates matters. The crux of the arrangement is that each should use the bike for the correct fraction of the distance. – true blue anil Jun 11 '16 at 09:10
  • @trueblueanil: No, I don't think so. Maybe it complicates matters if you broke it up into more trips, but maybe this gives you shorter solutions. If you think the minimal time needed to travel along the whole road depends only of the fraction of the distances the people uses the bike then you should show us a prove for this assumption. – miracle173 Jun 11 '16 at 09:45
  • @miracle173: If you work out the time taken by a person, there are two (fixed) speeds involved: riding speed and walking speed. The variable that changes the time taken is the fraction of distance riding and walking. I am not exactly into Russell's logical foundations of mathematics. – true blue anil Jun 11 '16 at 11:36
  • @moonshine: I think the bounty will be automatically awarded to you even if the answer is wrong. The other answer is wrong, too). This is because it is the answer with the highest votes and has more than 2 votes. It will be automatically assigned, if it is not manually assigned by the bounty owner – miracle173 Jun 12 '16 at 09:51
  • @trueblueanil: I can't see how your comment justifies that one has not to use these "complicate matters". If you change the problem to a simpler one then your answer may be a solution of the simpler problem but not of the original problem. – miracle173 Jun 12 '16 at 10:00
  • I shall be adding a new answer soon. Hopefully, it resolves all doubts. – true blue anil Jun 12 '16 at 10:50
0

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.

Henry
  • 157,058
  • 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. – miracle173 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. – Henry 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.. – miracle173 Jun 11 '16 at 05:18
-1

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$

true blue anil
  • 41,295
  • 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. – rkm0959 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 ? – true blue anil Jun 12 '16 at 12:28
  • I heard that faster solution exists – rkm0959 Jun 12 '16 at 12:30
  • I can't see how. We have fully utilized the bike for the two slowest walkers. – true blue anil Jun 12 '16 at 12:34
  • In fact, the division into two cases has been done to eliminate anomalous answers. If we dealt with the $a=2,b=5,c=10$ figures using case $2$, we would get $t \approx 2.47$, but the fraction of the distance utilized by the three would become meaningless. $f_2 +f_3$ would show around $147%$ utilization of the bike, and $f_1$ would become negative to compensate ! – true blue anil Jun 12 '16 at 13:54
  • assume at the t=0 the second walker uses the bike for 0.5 minutesto ride half the way. Then he leaves the bike and walks the remaining way in 2.5 minutes. So he needs 3.5 minutes. The third walker needs 1 minutes to arrive at the point where the bike was left and 0.5 minutes back to the start using the bike. Then he walks in 2 minutes to the end. These are 3.5 minutes. The first walker waits 1.5 minutes until the first walker has brought him the bike and then needs 1 minute to ride to the end. These are 2.5 minutes. So they need 3.5 minutes. This is less than the value you calculated – miracle173 Jun 12 '16 at 13:55
  • 1
    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. – rkm0959 Jun 12 '16 at 13:57
  • @miracle173: I agree that your solution gives a lower time. But then the million dollar question is: Is there a way to generalize for $a,b,c$ knowing only that $a<b<c$, and then evolve a formula for an overall time that is less than all of them (as was asked for) ??? – true blue anil Jun 12 '16 at 17:42
  • @trueblueanil: That's the question Gyumin Roh posed. I fear that he will not pay a million dollar for its solution. But he already gives a bounty of 50 points for it. – miracle173 Jun 12 '16 at 17:47