Men on a boat problem

Question

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?

Answer 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)

Answer 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$).