Thursday, June 05, 2008

Four Men across a Bridge Puzzle

Four men want to cross a bridge. However, the bridge is weak and they can only cross it two at a time. There is an additional complication. It is nighttime and they cannot cross the bridge in the darkness. Fortunately they do have a single flashlight with them. Clearly, only two men at a time can cross the bridge so one of them will have to return with the flashlight to take another man across and so on. The first man can cross the bridge in 1 minute, the second one in 2 minutes, the third one in 5 minutes and the fourth one in 10 minutes. When two people travel together they can only go as fast as the slowest person. For example, if the 1 min guy travels with the 10 min guy then they can get across only in 10 minutes.

What is the shortest time in which all of them can get across and how?

Brute Force Solution
The brute force solution to this puzzle is simple. Send the 1 min and the 10 min across. The 1 min guy comes back. This takes 11 minutes. Then send the 1 min and the 5 min guy across. The 1 min guy again comes back. This takes 5 minutes. Then send the 1 min and the 2 min guy across. This takes 2 minutes. The total is 11 + 6 + 3 = 19 minutes.

But as you can guess, that’s not the shortest time.

Real Solution
If you look at the problem carefully then you will realize that for each round trip, it is the slowest guy who is the bottleneck. So, instead of sending the 5 min and the 10 min guy separately, if we could send them both at the same time then we could save some time. However, it would make no sense to send them together and then ask the 5 min guy to come back because he will anyway have to cross once more which only increases the time take. Thus, we ought to have either the 1 min or the 2 min guy already standing at the other end when the 5 min and the 10 min guys reach together. Bingo! That’s our solution.

Send the one 1 min guy and the 2 min guy across. The 1 min guy returns. This takes 3 minutes. Then send the 5 min and the 10 min guys across. The 2 min guy returns. This takes 12 minutes. Then the 1 min and the 2 min guy go across again. This takes 2 minutes. The total is 3 + 12 + 2 = 17 minutes.

You can be happy now.

3 comments:

  1. u know what thanks and no thanks i cant believe i didnt figure that out ahh u put me at peace though

    ReplyDelete
  2. @ anonymous - Thanks and no thanks?

    ReplyDelete
  3. try this same algorithm again for the set of men whose time is 3, 4, 1, and 10.... I don't believe that the algorithm stated above is the shortest time. Infact if you send 1 back and forth each trip it works out to be shorter... why is this? how do you know which algorithm is shorter for each set of inputs?

    ReplyDelete