Bridge and torch problem

The second brain teaser is one of the river crossing puzzles. It’s another example in my opinion of an initially counter intuitive puzzle which becomes simple once you understand what assumption you should (or should not) be making. It’s most interesting in my opinion if you don’t know in advance in what time it can be solved, but instead try to figure out the minimal possible solution. I’ve seen a few people be utterly convinced their solution was the right one (unable to get out of the idea there might be a better one). Also note that with many of these problems it becomes much easier if you write down the options.

Four people come to a river in the night. There is a narrow bridge, but it can only hold two people at a time. They have one torch and, because it’s night, the torch has to be used when crossing the bridge. Person A can cross the bridge in one minute, B in two minutes, C in five minutes, and D in eight minutes. When two people cross the bridge together, they must move at the slower person’s pace. The question is, what is the fastest they can all get across?
Click for solution

An obvious first idea is that the cost of returning the torch to the people waiting to cross is an unavoidable price which should be minimized. This strategy makes A the torch bearer, shuttling each person across the bridge:

Elapsed Time Starting Side Action Ending Side
0 minutes A B C D
2 minutes       C D A and B cross forward, taking 2 minutes A B
3 minutes A    C D A returns, taking 1 minute    B
8 minutes          D A and C cross forward, taking 5 minutes A B C
9 minutes A       D A returns, taking 1 minute    B C
17 minutes A and D cross forward, taking 8 minutes A B C D

This strategy makes it possible to do a crossing in 17 minutes. To find the correct solution, one must realize that forcing the two slowest people to cross individually wastes time which can be saved if they both cross together:

Elapsed Time Starting Side Action Ending Side
0 minutes A B C D
2 minutes       C D A and B cross forward, taking 2 minutes A B
3 minutes A    C D A returns, taking 1 minute    B
11 minutes A C and D cross forward, taking 8 minutes    B C D
13 minutes A B B returns, taking 2 minutes       C D
15 minutes A and B cross forward, taking 2 minutes A B C D

A second equivalent solution swaps the return trips. Basically, the two fastest people cross together on the 1st and 5th trips, the two slowest people cross together on the 3rd trip, and EITHER of the fastest people returns on the 2nd trip, and the other fastest person returns on the 4th trip.

This problem (and the above solution) were taken from: https://en.wikipedia.org/wiki/Bridge_and_torch_problem. Check it out for more information about this problem and similar one’s.

image_pdfimage_print
Tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.