5

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?

Yoda
  • 477
  • 3
  • 9
  • 23

4 Answers4

10

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 ]

MJD
  • 65,394
  • 39
  • 298
  • 580
  • This is a better solution than mine, good work. – Asimov May 13 '14 at 00:16
  • 2
    3 and 4 can go back together, leaving 1 to cross without the lamp. After 4 trips, surely he's memorized the bridge by now? – Alex Shroyer May 13 '14 at 01:46
  • It might also be worth observing that if the times taken by the guys are more like $1,1,1,1\ldots 1000, 1000, 1000, \ldots 1000$ then the strategy of sending the slow guys over in pairs is a huge winner, as long as the slow guys don't outnumber the fast guys by too much. You send the fast guys in pairs, and the slow guys in pairs, and use the fast guys to bring the lamp back for the slow guys. – MJD May 13 '14 at 02:13
  • @MJD Could you post the greedy code you've created. I am programmer in the first place, does not matter what language. – Yoda May 13 '14 at 14:57
  • @Yoda https://github.com/mjdominus/perl-misc/blob/master/search/bridge – MJD May 13 '14 at 15:06
2

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!

Soumyadipto
  • 21
1

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.

Asimov
  • 3,024
  • 1
    There is a solution that uses only 31 units of time. They key is sending the two slowest guys together in one trip (of time $9$) instead of two separate trips (of time $8+9=17$). – MJD May 12 '14 at 23:00
  • That was my first impression, but then who carries the lamp back? Unless its the last trip, and then one of them had to go back, and that just seemed like a larger amount of time to me (not that i crunched the numbers) – Asimov May 12 '14 at 23:21
  • 1
    The fast guy stays over on one trip and carries the lamp back. – MJD May 12 '14 at 23:39
-1

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.

Phil
  • 1