Bridge crossing puzzle

Question

Four men have to cross a bridge at night.Any party who crosses, either one or two men, must carry the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, etc. Each man walks at a different speed. One takes 1 minute to cross, another 2 minutes, another 5, and the last 10 minutes. If two men cross together, they must walk at the slower man's pace. There are no tricks--the men all start on the same side, the flashlight cannot shine a long distance, no one can be carried, etc.

And the question is What's the fastest they can all get across. I am basically looking for some generalized approach to these kind of problem. I was told by my friend, that this can be solved by Fibonacci series, but the solution does not work for all.

Please note this is not a home work.

Answer 1

17 minutes - this is a classic MS question.

1,2 => 2 minutes passed.
1 retuns => 3 minutes passed.
5,10 => 13 minutes passed.
2 returns => 15 minutes passed.
1,2 => 17 minute passed.

In general the largest problem / slowest people should always be put together, and sufficient trips of the fastest made to be able to bring the light back each time without using a slow resource.

Answer 2

17 -- a very common question

-> 1-2 = 2
<- 2 = 2
-> 5,10 = 10 (none of them has to return)
<- 1 = 1
-> 1,2 = 2

all on the other side
total = 2+2+10+1+2 = 17

usually people get it as 19 in the first try

Answer 3

There is an entire PDF that solves the general case of this problem (in a formal proof).

Answer 4

I would solve this problem by placing a fake job ad on Dice.com, and then asking this question in the interviews until someone gets it right.

Answer 5

An exhaustive search of all possibilities is simple with such a small problem space. Breadth or depth first would work. It is a simple CS problem.

I prefer the missionary and cannibal problems myself