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?
Men on a boat problem
3
$\begingroup$
optimization
recreational-mathematics
-
0The 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
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$).
-
1can 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)
-
0This takes $32$ minutes for $n=4$, but in fact it can be done in $30$ minutes. – 2012-11-30