Bridge and torch problem

The bridge and torch problem (also known as The Midnight Train[1] and Dangerous crossing[2]) is a logic puzzle that deals with four people, a bridge and a torch.

There is a narrow bridge, and it can only hold two people at a time.

When two people cross the bridge together, they must move at the slower person's pace.

The question is, can they all get across the bridge if the torch lasts only 15 minutes?

[2] An obvious first idea is that the cost of returning the torch to the people waiting to cross is an unavoidable expense which should be minimized.

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:[4] A second equivalent solution swaps the return trips.

Assume that a solution minimizes the total number of crossings.

But, the time has elapsed and person A and B are still on the starting side of the bridge and must cross.

Then, A must cross next, since we assume we should choose the fastest to make the solo-cross.

[further explanation needed] In a variation called The Midnight Train, for example, person D needs 10 minutes instead of 8 to cross the bridge, and persons A, B, C and D, now called the four Gabrianni brothers, have 17 minutes to catch the midnight train.

In the case where there are an arbitrary number of people with arbitrary crossing times, and the capacity of the bridge remains equal to two people, the problem has been completely analyzed by graph-theoretic methods.

[4] Martin Erwig from Oregon State University has used a variation of the problem to argue for the usability of the Haskell programming language over Prolog for solving search problems.

[8] The puzzle is also mentioned in Daniel Dennett's book From Bacteria to Bach and Back as his favorite example of a solution that is counter-intuitive.