four friends a b c and d need to cross the bridge
Bridge and torch problem - wikipedia Bridge and torch problem Jump to : navigation , search The bridge and torch problem ( also known as The Midnight Train and Dangerous crossing ) is a logic puzzle that deals with four 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 . Contents ( hide ) 1 Story 2 Solution 3 A semi-formal approach 4 Variations and history 5 External links 6 See also 7 References Story ( edit ) 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 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 ? Variations of the story often indicate a reason why the bridge must be crossed in as short a time . For instance , in Ted - Ed 's version of the riddle , the oncoming approach of zombies necessitates a fast escape . Solution ( edit ) 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 . This strategy makes A the torch bearer , shuttling each person across the bridge : Elapsed Time Starting Side Action Ending Side 0 minutes ABCD 2 minutes CD A and B cross forward , taking 2 minutes AB 3 minutes A CD A returns , taking 1 minute B 8 minutes D A and C cross forward , taking 5 minutes ABC 9 minutes A D A returns , taking 1 minute BC 17 minutes A and D cross forward , taking 8 minutes ABCD 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 : Elapsed Time Starting Side Action Ending Side 0 minutes ABCD 2 minutes CD A and B cross forward , taking 2 minutes AB 3 minutes A CD A returns , taking 1 minute B 11 minutes C and D cross forward , taking 8 minutes BCD 13 minutes AB B returns , taking 2 minutes CD 15 minutes A and B cross forward , taking 2 minutes ABCD 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 . A semi-formal approach ( edit ) This section does not cite any sources . Please help improve this section by adding citations to reliable sources . Unsourced material may be challenged and removed . ( July 2014 ) ( Learn how and when to remove this template message ) Assume that a solution minimizes the total number of crosses . This gives a total of five crosses - three pair crosses and two solo - crosses . Also , assume we always choose the fastest for the solo - cross . First , we show that if the two slowest persons ( C and D ) cross separately , they accumulate a total crossing time of 15 . This is done by taking persons A , C , & D: C + A + B + A = 8 + 1 + 5 + 1 = 15 . ( Here we use A because we know that using A to cross both C and D separately is the most efficient . ) But , the time has elapsed and person A and B are still on the starting side of the bridge and must cross . So it is not possible for the two slowest ( C & D ) to cross separately . Second , we show that in order for C and D to cross together that they need to cross on the second pair - cross : i.e. not C or D , so A and B , must cross together first . Remember our assumption at the beginning states that we should minimize crosses and so we have five crosses - 3 pair - crossings and 2 single crossings . Assume that C and D cross first . But then C or D must cross back to bring the torch to the other side , and so whoever solo - crossed must cross again . Hence , they will cross separately . Also , it is impossible for them to cross together last , since this implies that one of them must have crossed previously , otherwise there would be three persons total on the start side . So , since there are only three choices for the pair - crossings and C and D can not cross first or last , they must cross together on the second , or middle , pair - crossing . Putting all this together , A and B must cross first , since we know C and D can not and we are minimizing crossings . Then , A must cross next , since we assume we should choose the fastest to make the solo - cross . Then we are at the second , or middle , pair - crossing so C and D must go . Then we choose to send the fastest back , which is B. A and B are now on the start side and must cross for the last pair - crossing . This gives us , B + A + D + B + B = 2 + 1 + 8 + 2 + 2 = 15 . Variations and history ( edit ) Several variations exist , with cosmetic variations such as differently named people , or variation in the crossing times or time limit . 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 . 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 . In all these variations , the structure and solution of the puzzle remain the same . Ted - ED posted a viral video variation of this problem where the crossing speeds are , in minutes , 1 , 2 , 5 , and 10 , and all must cross in 17 minutes . 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 . 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 . External links ( edit ) Slides of the Capacity C Torch Problem ( 1 ) Paper discussing the Capacity C Torch Problem ( 2 ) Ted Ed Video and Exercise Based on Bridge and Torch Problem ( 3 ) Paper discussing A Systematic Solution to the Bridge Riddle using Combinatorics ( 4 ) See also ( edit ) River crossing puzzle References ( edit ) ^ Jump up to : `` MURDEROUS MATHS BRAINBENDERS '' . Retrieved 2008 - 02 - 08 . ^ Jump up to : Gleb Gribakin . `` Some simple and not so simple maths problems '' . Retrieved 2008 - 02 - 08 . Jump up ^ Tricky Crossings , Ivars Peterson , Science News , 164 , # 24 ( December 13 , 2003 ) ; accessed on line February 7 , 2008 . ^ Jump up to : Rote , Günter ( 2002 ) . `` Crossing the bridge at night '' ( PDF ) . Bulletin of the European Association for Theoretical Computer Science . 78 . pp. 241 -- 246 . Jump up ^ `` The Bridge Crossing Puzzle '' . Archived from the original on 2008 - 05 - 31 . Jump up ^ Torsten Sillke ( September 2001 ) . `` Crossing the bridge in an hour '' . Retrieved 2008 - 02 - 09 . Jump up ^ Levmore , Saul X. ; Cook , Elizabeth Early ( 1981 ) . Super strategies for puzzles and games . Garden City , New York : Doubleday & Company . ISBN 0 - 385 - 17165 - X . Jump up ^ Erwig , Martin ( 2004 ) . `` Escape from Zurg '' ( PDF ) . Journal of Functional Programming , Vol. 14 , No. 3 . pp. 253 -- 261 . Retrieved from `` https://en.wikipedia.org/w/index.php?title=Bridge_and_torch_problem&oldid=792291130 '' Categories : Combinatorial optimization Logic puzzles Hidden categories : Articles needing additional references from July 2014 All articles needing additional references Talk Contents About Wikipedia Español Português Edit links This page was last edited on 25 July 2017 , at 17 : 38 . Text is available under the Creative Commons Attribution - ShareAlike License ; additional terms may apply . By using this site , you agree to the Terms of Use and Privacy Policy . Wikipedia ® is a registered trademark of the Wikimedia Foundation , Inc. , a non-profit organization . About Wikipedia
1. Bridge and torch problem
2. Logic puzzle
3. River crossing puzzles
4. Four people and a bridge
5. Crossing in 15 minutes or less