3
$\begingroup$

There is the usual question of some men on a boat- various men have various speeds, the boat has a capacity of 2 men, and the boat takes on the speed of the slowest man in the boat at any given time. Suppose we had $n$ men and 1 canoe with a capcity of two men, with the $nth$ man taking $2^n$ minutes to cross from one side to the next. What is the strategy to optimize the time to get all men to the other side?

  • 0
    The new URL for the document linked by @A.Schulz: [Crossing the Bridge at Night](https://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf) by Günter Rote, 2002.2016-10-11

2 Answers 2

2

Given the base case: $F(2)=2$ and $F(3)=2+1+4=7$.

And given that if you have $k$ man using the following greedy strategy:

  • send $1$ and $2$
  • then $1$ come back
  • sent the two slowest (for a time of $2^k$)
  • and then $2$ can come back
  • solve the smaller sub-problem (now you have the $k-2$ fastest men on one side, and the slowest two already passed, and you do not need them to take the boat back)

For example, for $4$ men: take $1$ and $2$ to the other side; come back with $1$; go to the other side with $3$ and $4$; go back with $2$; solve the sub-problem for $2$ men, that is just a trip of $1$ and $2$ for a total of $2+1+8+2+2=15$ time units.

This strategy is optimal (you never waste a transport), and for the time required this recursion holds: $F(n) = 2^k + 5 + F(n-2)$ (with the base case $F(3)=7$ and $F(4)=15$).

  • 1
    can we prove this to be the minimum?2012-11-30
-1

for two persons (speeds 2,4) - ans 4 mins

for 3 persons (speeds 2,4,8) - ans 2,4 go -> 4 ,2 comes back. next 2,8 go-> 8 so total 4+2+8

By Generalisation optimised time would be (2^2+2^3+......+2^n)+2*(n-2)

  • 0
    This takes $32$ minutes for $n=4$, but in fact it can be done in $30$ minutes.2012-11-30