Puzzle about six travellers going through bridge above canyon with an oil lamp

Question

There is a dark night and there is a very old bridge above a canyon. The bridge is very weak and only 2 men can stand on it at the same time. Also they need an oil lamp to see holes in the bridge to avoid falling into the canyon.

Six man try to go through that bridge. They need 1,3,4,6,8,9(first man, second man etc.) minutes to pass the bridge.

What is the fastest way for those six men to pass this bridge?

Answer 1

A minimal solution is:

• 1 and 6 cross the bridge; 1 comes back (7)
• 1 and 3 cross the bridge, 1 comes back (4)
• 8 and 9 cross the bridge; 3 comes back (12)
• 1 and 3 cross the bridge, 1 comes back (4)
• 1 and 4 cross the bridge (4)

Total is $7+4+12+4+4 = 31$. There are minor variations that are still minimal. For example, 3 can return in step 2 instead of in step 3.

I have nothing useful to say about how to find the solution; I programmed the computer to do an exhaustive search. I only posted this because the other guy was getting upvotes for his wrong answer.

[ By request, my search program is available ]

Answer 2

Obviously one person will need to go back and forth, taking people across, and then bringing the lamp back. This person will take the most trips, and should be the fastest person (the 1). What he does is guide person 2 across, runs back, guides person 3 across etc. until all are across.

Take 3 across (3 MIN) Run Back (1 MIN) Take 4 across (4 MIN) Run Back (1 MIN) Take 6 across (6 MIN) Run Back (1 MIN) Take 8 across (8 MIN) Run Back (1 MIN) Take 9 across (9 MIN)

$3+1+4+1+6+1+8+1+9=34$

34 minutes is the best time I can think of.

Answer 3

The correct answer is 31 minutes. This is a very common puzzle question which has been included in various books on brain-teasers, and a few mini games are also based on this puzzle.

The basic trick here is that 1, being the fastest, should ideally cross the bridge with each of the others, so that bringing back the lamp will take the least time. However, the important catch here is that the two slowest people(8 and 9) should always cross together, with one of the faster people waiting on the other side to bring the lamp back. This is due to the fact that if they go separately, it will take 8+9 = 17 minutes to cross, plus additional time to bring the lamp back. If they go together, however, it will take only 9 minutes, and even if the next slowest person(6) brings the lamp back, it will only take 9+6 = 15 minutes.

The algorithm for the solution is as follows (One can make minor variations to this without changing the outcome) : 1> 1 and 3 cross, 3 brings back the lamp : 3+3 = 6 minutes. 2> 8 and 9 cross, 1 brings back the lamp : 9+1 = 10 minutes. 3> 1 and 3 cross, 1 brings back the lamp : 3+1 = 4 minutes. 4> 1 and 4 cross, 1 brings back the lamp : 4+1 = 5 minutes. 5> 1 and 6 cross - everyone has reachedthe other side : 6 minutes Total time = 6 + 10 + 4 + 5 + 6 = 31 minutes

So the basic trick is to make the two slowest people cross only once, together. Cheers!

Answer 4

A minimal solution is:

1 and 3 cross the bridge; 1 comes back (4) 12 and 8 cross the bridge, 3 comes back (15) 1 and 6 cross the bridge; 1 comes back (7) 1 and 3 cross the bridge (3) Total is 4+15+7+3=29.