Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Bridge crossing puzzle

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.

like image 220
Ganesh M Avatar asked Jul 17 '09 16:07

Ganesh M


2 Answers

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

like image 68
Matthew Jones Avatar answered Oct 19 '22 17:10

Matthew Jones


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.

like image 33
Andrew Avatar answered Oct 19 '22 15:10

Andrew