5

Three men want to travel from town $P$ to town $Q$ (distance between towns: $a$). They have a motorbike (vehicle speed: $b$), but only two of them can be on the motorbike at the same time. Their walking speed is $c$ ($b$ > $c$). How much time do they need to travel? I believe that the best solution goes like this:

  1. Two people ($A$ and $B$) travel on motorbike, the third one ($C$) walks.
  2. $A$ drops $B$ at point $X$ and goes back to pick up $C$. $B$ walks to town $Q$.
  3. After picking up $C$, motorbike goes to town $Q$. All three men arrive at the same time.

However, I don't know, how to prove that this is the best solution.

N. F. Taussig
  • 76,571
Rakaho
  • 105
  • 4

1 Answers1

4

We may assume $a=1$, $b=1$ and $c={1\over w}$, whereby $w>1$ denotes the time needed to walk the full stretch. In order to simplify matters I'm assuming that $A$ is always staying with his bike. Given some protocol ${\cal P}$ (maybe more complicated than the one described in the question), denote by $t_A$, $t_B$, $t_C$ the time needed by the three people in order to arrive at $Q$, when this protocol is in force. We want a universal lower bound for the quantity $$T_{\cal P}:=\max\{t_A,t_B,t_C\}\ .$$ Let $\rho_B$ be the fraction of the way $B$ is riding forward on the bike together with $A$, and define $\rho_C$ similarly. Then $$t_B\geq \rho_B+(1-\rho_B)w=w-(w-1)\rho_B,\qquad t_C\geq w-(w-1)\rho_C\ .$$ It follows that $$\max\{t_B,t_C\}\geq w-(w-1)\min\{\rho_B,\rho_C\}\geq w-(w-1)\rho\ ,\qquad \rho:={\rho_B+\rho_C\over2}\ .\tag{1}$$ In order to get a bound for $t_A$ we have to distinguish the cases (i): $\rho_B+\rho_C\leq1$ and (ii): $\rho_B+\rho_C>1$. In case (i) all we can say is $t_A\geq1$. In case (ii) the parts of the road where $B$ as well as $C$ are riding with $A$ overlap by at least $\rho_B+\rho_C-1$. It follows that $A$ has to drive back at least this amount. In this way we obtain in case (ii) the bound $$t_A\geq\rho_B+\rho_C+(\rho_B+\rho_C-1)=4\rho-1\ .$$ It is therefore safe to say that $$t_A\geq\max\{1,4\rho-1\}\ .\tag{2}$$ Taking $(1)$ and $(2)$ together we see that $$T_{\cal P}\geq\max\{w-(w-1)\rho, 1,\ 4\rho-1\}\ .\tag{3}$$ An analysis of $(3)$ for $0\leq\rho\leq1$ then shows that the RHS is minimal at $\rho={w+1\over w+3}$. This leads to the universal estimate $$T_{\cal P}\geq{3w+1\over w+3}\ .$$ I'd say that the protocol you describe realizes this bound; hence you cannot do better.

Christian Blatter
  • 226,825