Bridge and torch problem

From Wikipedia, the free encyclopedia

The bridge and torch problem (also known as The Midnight Train[1] and Dangerous crossing[2]) is a logic puzzle that deals with 4 people, a bridge and a torch. It is one of the category of river crossing puzzles, where a number of objects must move across a river, with some constraints.[3]

Contents

[edit] Story

Four people come to a river in the night. There is a narrow bridge, but it can only hold two people at a time. Because it's night, the torch has to be used when crossing the bridge. Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. 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 in 15 minutes or less?[2]

[edit] Solution

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

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 does not permit a crossing in 15 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:[4]

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

[edit] Variations and history

Several variations exist, with cosmetic variations such as differently named people, or variation in the crossing times or time limit.[5] The torch itself may expire in a short time and so serve as the time limit. 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.[1]

The puzzle is known to have appeared as early as 1981, in the book Super Strategies For Puzzles and Games. In this version of the puzzle, A, B, C and D take 5, 10, 20, and 25 minutes, respectively, to cross, and the time limit is 60 minutes.[6][7] In all these variations, the structure and solution of the puzzle remain the same.

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]

[edit] See also

[edit] References

  1. ^ a b MURDEROUS MATHS BRAINBENDERS. Retrieved on 2008-02-08.
  2. ^ a b Gleb Gribakin. Some simple and not so simple maths problems. Retrieved on 2008-02-08.
  3. ^ Tricky Crossings, Ivars Peterson, Science News, 164, #24 (December 13, 2003); accessed on line February 7, 2008.
  4. ^ a b c Rote, Günter (2002), “Crossing the bridge at night”, Bulletin of the European Association for Theoretical Computer Science 78: 241–246, <http://page.mi.fu-berlin.de/%7Erote/Papers/pdf/Crossing+the+bridge+at+night.pdf> 
  5. ^ The Bridge Crossing Puzzle.
  6. ^ Torsten Sillke (September 2001). Crossing the bridge in an hour. Retrieved on 2008-02-09.
  7. ^ Levmore, Saul X. & Cook, Elizabeth Early (1981), Super strategies for puzzles and games, Garden City, New York: Doubleday & Company, ISBN 0-385-17165-X