Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Is dynamic programming of any help here? –  bonext Nov 30 '12 at 15:28
    
-I was thinking of more of a mathematical, intuitive approach, but I do not mean non-rigorous by intuitive. –  Johann Linus Nov 30 '12 at 16:20
    
Is there a consistent strategy that yields the minimum time for all n? –  Johann Linus Nov 30 '12 at 16:23
1  
This might be helpful. –  A.Schulz Nov 30 '12 at 17:01
add comment

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

share|improve this answer
    
And from there a closed formula can be easily found... –  carlop Nov 30 '12 at 17:07
1  
can we prove this to be the minimum? –  Johann Linus Nov 30 '12 at 19:57
add comment

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)

share|improve this answer
    
This takes $32$ minutes for $n=4$, but in fact it can be done in $30$ minutes. –  Chris Eagle Nov 30 '12 at 16:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.