564:
a total crossing time of 15. This is done by taking persons A, C, & D: C+A+D+A = 5+1+8+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 crossings and so we have five crossings - 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 cannot 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 cannot 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.
20:
503:
78:
Four people come to a river in the night. There is a narrow bridge, and 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.
563:
Assume that a solution minimizes the total number of crossings. This gives a total of five crossings - three pair crossings and two solo-crossings. 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
293:
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.
572:
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
87:
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:
584:. 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.
190:
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:
587:
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
577:, 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.
417:
488:
333:
79:
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?
827:
594:
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
524:
856:
737:
685:
789:
550:
603:
528:
513:
716:
532:
517:
339:
422:
861:
837:
756:
616:
67:
300:
806:
785:
297:
Thus the minimum time for four people is given by the following mathematical equations: When
741:
682:
832:
689:
19:
663:
595:
850:
778:
639:
588:
59:
841:
Paper discussing A Systematic
Solution to the Bridge Riddle using Combinatorics
502:
70:, where a number of objects must move across a river, with some constraints.
812:. Journal of Functional Programming, Vol. 14, No. 3. pp. 253–261.
842:
724:
Bulletin of the
European Association for Theoretical Computer Science
580:
The puzzle is known to have appeared as early as 1981, in the book
63:
18:
607:
as his favorite example of a solution that is counter-intuitive.
496:
700:, #24 (December 13, 2003); accessed on line February 7, 2008.
836:
Ted Ed Video and
Exercise Based on Bridge and Torch Problem
151: D
23:
The two solutions with the vertical axis denoting time,
601:
The puzzle is also mentioned in Daniel
Dennett's book
425:
342:
303:
784:. Garden City, New York: Doubleday & Company.
777:
482:
411:
327:
776:Levmore, Saul X.; Cook, Elizabeth Early (1981).
426:
343:
831:Paper discussing the Capacity C Torch Problem
664:"Some simple and not so simple maths problems"
165:A D
8:
62:that deals with four people, a bridge and a
531:. Unsourced material may be challenged and
551:Learn how and when to remove this message
424:
412:{\displaystyle \min(B+A+C+A+D,B+A+D+B+B)}
341:
302:
284:A and B cross forward, taking 2 minutes
257:C and D cross forward, taking 8 minutes
229:A and B cross forward, taking 2 minutes
226: C D
193:
181:A and D cross forward, taking 8 minutes
154:A and C cross forward, taking 5 minutes
126:A and B cross forward, taking 2 minutes
123: C D
90:
826:Slides of the Capacity C Torch Problem
710:
708:
706:
657:
655:
628:
780:Super strategies for puzzles and games
582:Super Strategies For Puzzles and Games
483:{\displaystyle \min(2A+B+C+D,A+3B+D)}
7:
634:
632:
529:adding citations to reliable sources
274: C D
14:
755:Torsten Sillke (September 2001).
726:. Vol. 78. pp. 241–246.
757:"Crossing the bridge in an hour"
501:
328:{\displaystyle A<B<C<D}
717:"Crossing the bridge at night"
640:"MURDEROUS MATHS BRAINBENDERS"
604:From Bacteria to Bach and Back
477:
429:
406:
346:
1:
738:"The Bridge Crossing Puzzle"
271:B returns, taking 2 minutes
66:. It is in the category of
243:A returns, taking 1 minute
168:A returns, taking 1 minute
140:A returns, taking 1 minute
878:
857:Combinatorial optimization
240:A C D
137:A C D
48:bridge and torch problem
805:Erwig, Martin (2004).
568:Variations and history
493:A semi-formal approach
484:
413:
329:
171: B C
68:river crossing puzzles
43:
715:Rote, Günter (2002).
617:River crossing puzzle
485:
414:
330:
22:
525:improve this section
423:
340:
301:
246: B
143: B
260: B C D
807:"Escape from Zurg"
692:, Ivars Peterson,
688:2008-01-20 at the
575:The Midnight Train
480:
409:
325:
56:Dangerous crossing
52:The Midnight Train
44:
561:
560:
553:
291:
290:
188:
187:
869:
814:
813:
811:
802:
796:
795:
783:
773:
767:
766:
764:
763:
752:
746:
745:
740:. Archived from
734:
728:
727:
721:
712:
701:
683:Tricky Crossings
680:
674:
673:
671:
670:
659:
650:
649:
647:
646:
636:
556:
549:
545:
542:
536:
505:
497:
489:
487:
486:
481:
418:
416:
415:
410:
334:
332:
331:
326:
194:
91:
42:
35:
29:
877:
876:
872:
871:
870:
868:
867:
866:
847:
846:
823:
818:
817:
809:
804:
803:
799:
792:
775:
774:
770:
761:
759:
754:
753:
749:
736:
735:
731:
719:
714:
713:
704:
690:Wayback Machine
681:
677:
668:
666:
662:Gleb Gribakin.
661:
660:
653:
644:
642:
638:
637:
630:
625:
613:
596:search problems
589:graph-theoretic
570:
557:
546:
540:
537:
522:
506:
495:
421:
420:
419:
338:
337:
336:
299:
298:
85:
76:
50:(also known as
37:
30:
24:
17:
12:
11:
5:
875:
873:
865:
864:
859:
849:
848:
845:
844:
839:
834:
829:
822:
821:External links
819:
816:
815:
797:
790:
768:
747:
744:on 2008-05-31.
729:
702:
675:
651:
627:
626:
624:
621:
620:
619:
612:
609:
569:
566:
559:
558:
509:
507:
500:
494:
491:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
324:
321:
318:
315:
312:
309:
306:
289:
288:
285:
282:
280:
276:
275:
272:
269:
266:
262:
261:
258:
255:
252:
248:
247:
244:
241:
238:
234:
233:
230:
227:
224:
220:
219:
217:
215:
212:
208:
207:
204:
201:
200:Starting Side
198:
186:
185:
182:
179:
177:
173:
172:
169:
166:
163:
159:
158:
155:
152:
149:
145:
144:
141:
138:
135:
131:
130:
127:
124:
121:
117:
116:
114:
112:
109:
105:
104:
101:
98:
97:Starting Side
95:
84:
81:
75:
72:
15:
13:
10:
9:
6:
4:
3:
2:
874:
863:
862:Logic puzzles
860:
858:
855:
854:
852:
843:
840:
838:
835:
833:
830:
828:
825:
824:
820:
808:
801:
798:
793:
791:0-385-17165-X
787:
782:
781:
772:
769:
758:
751:
748:
743:
739:
733:
730:
725:
718:
711:
709:
707:
703:
699:
695:
691:
687:
684:
679:
676:
665:
658:
656:
652:
641:
635:
633:
629:
622:
618:
615:
614:
610:
608:
606:
605:
599:
597:
592:
590:
585:
583:
578:
576:
567:
565:
555:
552:
544:
534:
530:
526:
520:
519:
515:
510:This section
508:
504:
499:
498:
492:
490:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
322:
319:
316:
313:
310:
307:
304:
295:
286:
283:
281:
278:
277:
273:
270:
267:
264:
263:
259:
256:
253:
250:
249:
245:
242:
239:
236:
235:
231:
228:
225:
222:
221:
218:
216:
213:
210:
209:
205:
202:
199:
197:Elapsed Time
196:
195:
192:
183:
180:
178:
175:
174:
170:
167:
164:
161:
160:
156:
153:
150:
147:
146:
142:
139:
136:
133:
132:
128:
125:
122:
119:
118:
115:
113:
110:
107:
106:
102:
99:
96:
94:Elapsed Time
93:
92:
89:
82:
80:
73:
71:
69:
65:
61:
57:
53:
49:
40:
33:
27:
21:
800:
779:
771:
760:. Retrieved
750:
742:the original
732:
723:
697:
694:Science News
693:
678:
667:. Retrieved
643:. Retrieved
602:
600:
593:
586:
581:
579:
574:
571:
562:
547:
538:
523:Please help
511:
296:
292:
206:Ending Side
189:
103:Ending Side
86:
77:
60:logic puzzle
55:
51:
47:
45:
38:
31:
25:
16:Logic puzzle
279:15 minutes
265:13 minutes
251:11 minutes
176:17 minutes
851:Categories
762:2008-02-09
669:2008-02-08
645:2008-02-08
623:References
237:3 minutes
223:2 minutes
211:0 minutes
162:9 minutes
148:8 minutes
134:3 minutes
120:2 minutes
108:0 minutes
34:the finish
28:the start,
591:methods.
541:July 2014
512:does not
41:the torch
686:Archived
611:See also
287:A B C D
214:A B C D
184:A B C D
111:A B C D
83:Solution
533:removed
518:sources
203:Action
100:Action
58:) is a
788:
157:A B C
810:(PDF)
720:(PDF)
74:Story
64:torch
786:ISBN
516:any
514:cite
320:<
314:<
308:<
268:A B
232:A B
129:A B
54:and
46:The
36:and
698:164
527:by
427:min
344:min
853::
722:.
705:^
696:,
654:^
631:^
598:.
335:,
254:A
794:.
765:.
672:.
648:.
554:)
548:(
543:)
539:(
535:.
521:.
478:)
475:D
472:+
469:B
466:3
463:+
460:A
457:,
454:D
451:+
448:C
445:+
442:B
439:+
436:A
433:2
430:(
407:)
404:B
401:+
398:B
395:+
392:D
389:+
386:A
383:+
380:B
377:,
374:D
371:+
368:A
365:+
362:C
359:+
356:A
353:+
350:B
347:(
323:D
317:C
311:B
305:A
39:T
32:f
26:s
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
