Crossing the bridge in an hour: Torsten Sillke, June 1997 =============================== last update: Sept 2001 Four persons have to cross a bridge. The times each needs to cross it are: 5 min, 10 min, 20 min, and 25 min. It is dark and they only have one lamp, we have the following constraints: - the bridge can only be crossed if one has a lamp, while it is too dark. - 2 persons at most are allowed to be on the bridge at the same time. - the speed of a pair is determined by the speed of the slower person. - the lamp can last only an hour. - the lamp cannot be thrown. How do they manage to cross the river within an hour? << This is no trick question. >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Who knows the origin of this puzzle? My oldest written form is 1981 References: - Saul X. Levmore and Elizabeth Early Cook Super Strategies For Puzzles and Games, Doubleday & Company, Inc, Garden City, New York 1981 ISBN 0-385-17165-X, p3 - Martin Erwig Fernuni Hagen, Wintersemester 92/93, October 1992, Kurs: 1663 Datenstrukturen, Kurseinheit 04, 1663-3-04-A1 Aufgabe 2 mailto:Martin.Erwig@FernUni-Hagen.de - Dick Hess Puzzles From Around the World, April 1997, self-distributed. problem 107: The Bridge mailto:RIHess@compuserve.com - no name Brainteasers B 205: Family planning Quantum (May/June 1997) 13 http://www.nsta.org/quantum/bridgarc.asp Quantum CyberTeaser: May/June 1997 - Matthew Daly (Mon August 25 1997) (mailto:mwdaly@kodak.com) [FAQ] rec.puzzles Frequently Asked Questions [weekly] Rec-puzzles-archive-name: puzzles/faq Last-modified: Mon August 25 1997 << first appearence in this FAQ>> Version: 1.335 2.6 How quickly can the four men cross the bridge? - Heinrich Hemme bild der wissenschaft, Februar 1998, S. 110 (Cogito Problem) bild der wissenschaft, Mai 1998, S. 111 (Solution) mailto:Hemme@fh-aachen.de - Heinrich Hemme Das Problem des Zw\"olf-Elfs, Vandenhoeck & Ruprecht, 1998, ISBN 3-525-40736-X Problem 81: Die Flucht - Heinrich Hemme; Mensch, \"argere dich nicht, 72 Kopfn\"usse und Knobeleien f\"ur jede Gelegenheit, ro ro ro science, Hamburg, 2003, ISBN 3-499-61575-4 - p48-49, 160-161 M\"unchhausens H\"angebr\"ucke - Bernhard Wiezorke Puzzles und Brainteasers, OR News, M\"arz 1998, S. 52 (Problem, Dick Hess version) - Thomas von Randow Zeit-Magazin, Nr. 21, 14. Mai 1998, S. 34 (Zweistein Problem) Zeit-Magazin, Nr. 22, 20. Mai 1998, S. 36 (Solution) - David Chews IQMASTER FORUM Points of View, http://www.serve.com/davidchew/cgi-bin/iqchat/iqchattable.cgi - plastelina games http://www.plastelina.net/examples/games/game3.html (2001) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Other Versions of the same puzzle: - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Super Strategies For Puzzles and Games by Saul X. Levmore and Elizabeth Early Cook, 1981, p3 Four men must cross a bridge over a deep ravine in enemy territory in the middle of the night. The treacherous bridge will hold only two men at once and it is necessary to carry a lantern while crossing. One of the men takes 5 minutes for the trip accross. one takes 10, a third man requires 20, and the last needs 25 minutes. Unfortunately, they have only one lantern among them. How can they make it across if they have only 60 minutes before the bridge is blown up? - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - european version: (from rec.puzzles, Sept. 1997) Bridge. Midnight. New moon. Overcast. 4 people have to cross the bridge: Child, Father, Uncle, Grandpa. All they have is a single flashlight and for some reason they know that the batteries will last for exactly 60 minutes. The bridge can carry only two persons at a time - strange enough, it depends only on the *number*, not on the *weight* of the people... ;-) However, each person takes a different amount of time to cross the bridge: Child: 5 min Father: 10 min Uncle: 20 min Grandpa: 25 min In what order do they have to cross the bridge so that nobody is on the bridge in the dark - *and* the flashlight doesn't burn out before they all reached the other side? ...oh yes, I forgot to mention: it is also quite foggy, the beam of the flashlight cannot be seen for more than a few meters - the bridge is far longer. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Brainteasers B 205: Family planning, Quantum (May/June 1997) 13 Family planning. A Family of four (father, mother, son, and daughter) went on a hike. They walked all day long and, when evening was already drawing on, came to an old bridge over a deep gully. It was very dark and they had only one latern with them. The bridge was so narrow and shaky that it could hold no more than two persons at a time. Suppose it takes the son 1 minute to cross the bridge, the daugher 3 minutes, the father 8 minutes, and the mother 10 minutes. Can the entier family cross the bridge in 20 minutes? If so how? (When any two persons cross the bridge, their speed is equal to that of the slower one. Also the latern must be used while crossing the bridge.) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Dick Hess, Puzzles From Around the World, April 1997, problem 107: The Bridge Four men must cross a bridge. They all begin on the same side and have 17 minutes to get across. It is night and they need their one flashlight to guide them on any crossing. A maximum of two poeple can cross at one time. Each man walks at a different speed: Man 1 takes 1 minute to cross; Man 2 takes 2 min.; Man 3 takes 5 min. and Man 4 takes 10 min. A pair must walk together at a rate of the slower man's pace. Try these other problems. (a) There are 6 men with crossing times of 1,3,4,6,8,9 min. [cross in 31 min.] (b) There are 7 men with crossing times of 1,2,6,7,8,9,10 min. and the bridge will hold up to 3 men at a time. [cross in 25 min.] - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - [FAQ] rec.puzzles Frequently Asked Questions [weekly] Last-modified: Mon August 25 1997 << first appearence in this FAQ >> Version: 1.335 2.6. Four men are on one side of a rickety bridge on a dark night. The bridge is only strong enough to support two men at a time. It is also necessary for the men crossing the bridge to carry a lantern to guide their way, and the four men have only one lantern between them. Andy can cross the bridge in 1 minute, Ben in 2, Charlie in 5, and Dan in ten minutes. How quickly can all four men be together at the other side? The solution is surprising to some people because they initially suspect that it is fastest if Andy escorts everyone across because he can return the fastest. However, a faster method requires only 17 minutes. First, Andy and Ben cross (2 min), then Andy returns (1 min). Then, Charlie and Dan cross (10 min) and Ben returns (2 min). Finally, Andy and Ben recross (2 min). In short, you save two minutes by having the two slowest people cross the bridge in the same trip. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - This is a test that Microsoft apparently ask potential employees. I must warn you, you can really get caught up trying to solve this problem. Reportedly, one guy solved it by writing a C program, although that took him 37 minutes to develop (compiled and ran on the 1st try though). Another guy solved it in three minutes. A group of 50, at Motorola, couldn't figure it out at all. See how long it takes you. The Puzzle U2 has a concert that starts in 17 minutes and they must all cross a bridge to get there. All four men begin on the same side of the bridge. You must help them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each band member walks at a different speed. A pair must walk together at the rate of the slower man's pace: Bono:- 1 minute to cross Edge:- 2 minutes to cross Adam:- 5 minutes to cross Larry:- 10 minutes to cross For example: if Bono and Larry walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Larry then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. Notes: There is no trick behind this. It is the simple movement of resources in the appropriate order. There are two known answers to this problem. This is based on a question Microsoft gives to all prospective employees. Note: Microsoft expects you to answer this question in under 5 minutes! - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Martin Erwig, Fernuni Hagen, Wintersemester 92/93, October 1992 Vier Personen (A, B, C und D) besitzen eine Fackel mit maximaler Brenndauer von 60 Minuten, mit der sie eine Bruecke in der Dunkelheit ueberqueren sollen. Aufgrund ihrer verschiedenen koerperlichen Konstitutionen benoetigen sie unterschiedlich lange fuer einen Weg ueber die Bruecke: A benoetigt 5 Minuten, B benoetigt 10 Minuten, C benoetigt 20 Minuten, und D benoetigt 25 Minuten. Die Bruecke ist nicht sehr stabil, so dass sich maximal zwei Personen gleichzeitig auf der Bruecke befinden duerfen. Wenn zwei Personen die Bruecke ueberqueren, geht dies natuerlich nur so schnell wie es die langsamere Person kann. Das Problem ist nun: In welcher Reihenfolge muessen A, B, C und D ueber die Bruecke gehen, damit sie innerhalb der Brenndauer der Fackel alle hinuebergelangen koennen? - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Heinrich Hemme, Das Problem des Zw\"olf-Elfs, 1998, Problem 81: Die Flucht Vier Forscher sind mitten in der Nacht im Dschungel auf der Flucht vor einem kriegerischen Stamm. Sie kommen an einem reissenden Fluss, \"uber den nur eine schmale H\"angebr\"ucke ohne Gel\"ander f\"uhrt. Man sieht der Br\"ucke an, dass sie h\"ochstens zwei Personen tr\"agt und dass man ohne Licht nicht ans andere Ufer kommt. Die Forscher m\"ussen m\"oglichst schnell den Fluss \"uberqueren, da die Krieger ihnen schon auf den Fersen sind. Sie haben aber nur eine einzige Taschenlampe bei sich und ben\"otigen, da nicht alle gleich sportlich sind, unterschiedlich lange f\"ur einen Weg \"uber die Br\"ucke: Einer braucht zwei Minuten, einer vier Minuten, einer acht Minuten und einer zehn Minuten. Wie schnell k\"onnen es die vier Forscher schaffen, alle \"uber den Fluss zu kommen? - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Pythagoras interactief: het hangbrug-probleem (oktober 2000) De vier leden van een beroemde popgroep hebben voor hun optreden een uitstapje gemaakt. 's Avonds laat zijn ze verdwaald en staan ze voor een onbetrouwbare hangbrug. Over 17 minuten begint hun optreden. Het oversteken van de hangbrug kan maar op een manier: Kun jij de bandleden helpen de oversteek te maken in 17 minuten? Selecteer de personen die je wil laten oversteken en klik op "Go". Succces! - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Plastelina games http://www.plastelina.net/examples/games/game3.html Please help this family to cross to the other side of the bridge. Notice that: It is night. There is 1 lamp. A maximum of 2 persions can cross at one time, and they must have the lamp with them. Each person walks at a different speed: 1sec 3 sec 6sec 8sec 12sec. A pair must walk together at the rate of the slower person. The lamp enough for 30 sec only!!! - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - S P O I L E R - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Date: 17 Sep 1997 01:12:49 GMT From: karenl@onayamspay.SLAC.Stanford.EDU (Karen L Lingel) Organization: Stanford Linear Accelerator Center Newsgroups: rec.puzzles FOUR HUNGRY MEN CROSS A BRIDGE by Karen Lingel, Physicist and Penguinist Four men start out to cross the sea And yet they all walk different speeds! The first, a sprinter, he goes fast He leaves the others in the past! The second takes a bit more time [Note to myself: think up a rhyme] The third's a somewhat pokey man He strolls along, sees what he can. The last one is so very slow You'd think he had no place to go! So now they come upon a bridge And on the other side -- a fridge! Well -- you know men -- they've gotta see What's inside the fridge to eat! One flashlight is the light they've got To guide them to the eating spot. The batteries will only last Twenty minutes -- that's a fact. The bridge, alas, -- and here's the trap -- Is apparently a piece of crap. So only two men at a time can cross the bridge -- or they'll sink in brine! How can they all then make the trip? And use the light so no one slips? Send the fast guys first across The fastest returns with little loss. The pokey ones are next to go While Fast Guy waits (they sure are slow) Then send the other fast guy back To get his friend and complete the pack. And this rounds out, for all to see Another FAQ in poetry. Thank you, thank you. -k- -------------------------------------- Karen Lingel, Physicist and Penguinist - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Solution: If n persons {1..n} with walking times: t(1) <= t(1) total time: t(1) n=2: crossing time {1, 2} -> t(2) total time: t(2) n=3: crossing time {1, 2} -> t(2) {1} <- t(1) {1, 3} -> t(3) total time: t(1) + t(2) + t(3) n>3: Induction step: n -> n-2 case: I case: II crossing time crossing time {1, 2} -> t(2) {1, n} -> t(n) {1} <- t(1) {1} <- t(1) {n-1, n} -> t(n) {1, n-1} -> t(n-1) {2} <- t(2) {1} <- t(1) total time of this part: t(1) + t(n) + Min( 2*t(2), t(1) + t(n-1) ) (For t1=5, t2=10, t3=20, and t4=25 we have: 5+25+Min(2*10,5+20) = 50) So the slow ones walk in pairs the faster ones go with the fastest. Exercise: proof the optimality of the schedule given above. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Other walking times in use: t : (1,2,3,4) = (5,10,20,25) min ct = 60 // European version t : (1,2,3,4) = (1,2,5,10) min ct = 17 // American version t : (1,2,3,4) = (2,3,5,8) min ct = 19 // Torsten Sillke t : (1,2,3,4) = (2,2,3,3) min ct = 11 // Torsten Sillke t : (1..5) = (1,3,6,8,12) min ct = 29 // Plastelina t : (1..6) = (1,3,4,6,8,9) min ct = 31 // Dick Hess (min ct is the minimal crossing time.) Generalized Problems: - k persons at most are allowed to be on the bridge at the same time. - A fixed subset A of {1..n} is allowed to carry the lamp. We have a partial greedy structure but up to now I can't give an optimal schedule. Special case: t(1)=t(2)=0 In this case the transportation of the lamp is for free. Then let always the remaining k slowest walk. Example: smaller group may be faster From the special case (t(1)=t(2)=0) we derive an example, where more crossings are better (if t(1)>0). - Let k = 3 and t : (1,2,3,4,5,6,7) = (5,5,20,20,25,25,25) min ct = 70 // Torsten Sillke t : (1,2,3,4,5,6,7) = (1,2,6,7,8,9,10) min ct = 25 // Dick Hess TS DH {1,2} -> 5 2 {1} <- 5 1 {5,6,7} -> 25 10 {2} <- 5 2 {1,3,4} -> 20 7 {1} <- 5 1 {1,2} -> 5 2 -------- 70 25 are faster than {1,2,4} -> 20 7 {1} <- 5 1 {5,6,7} -> 25 10 {2} <- 5 2 {1,2,3} -> 20 6 -------- 75 26 or {1,6,7} -> 25 10 {1} <- 5 1 {1,4,5} -> 25 8 {1} <- 5 1 {1,2,3} -> 20 6 -------- 80 26 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ----- Whom I have asked? -- the reactions ----- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- Chris Cole -- (30 May 1997) Yes, I still maintain the [rec.puzzles] archive. We have seen this problem or its close relatives several times in the last few years. However, I have not seen anyone try to track it to its original version. It may be quite old, as it is easy to state but hard to solve. Such problems tend to be rare and ancient. mailto:chris@questrel.questrel.com -- Jerry Slocum -- (8 Jun 1997) Sorry, but I do not know any of the history of the "Crossing the bridge" problem. I have asked Dick Hess also but he does not know the history either. mailto:Jerry_Slocum@compuserve.com -- Richard Guy -- (23 Jun 1997) Looks a nice puzzle. I don't remember seeing anything like it before. RKG. mailto:rkg@cpsc.ucalgary.ca -- David Singmaster -- (25 Jun 1997) I learned of this problem about a year or two ago, but from a friend, possibly David Wells. I have no references for it! I'm seeing David on Sunday and some other people, so I'll try to remember to ask them. mailto:David.Singmaster@sbu.ac.uk -- Matthew Daly -- (31 Jul 1997, in rec.puzzles) Actually, there are a number of very clever and oft-posted puzzles that just weren't widely distributed before the most recent revision of the archive [of rec.puzzles]. The three that I can think of are: 1) The four men crossing a bridge with a lantern 2) The three light bulbs with switches in a different room (seen elsewhere in the current feed) 3) The voting pirates distributing a treasure of gold pieces. mailto:mwdaly@kodak.com (Matthew Daly) -- Zweistein (Thomas v. Randow) -- (3 Sep 1997) Nein, ich habe das Raetsel bislang niergendwo gelesen. mailto:LOGELEI@aol.com -- Udo Sprute -- (ca 1993) I know it for several years and head it in some variations. But the times were always the same. trace back: <- Ingo Kaup, G"utersloh, Germany (ca 1985) <- Roland Wenner, G"utersloh, Germany, Schr"odinger Weg, 05241/40585 (ca 1985) mailto:sprute@mathematik.uni-bielefeld.de -- Torsten Sillke -- (1996) trace back: <- Wolfgang Schneider, Frankenberg (Eder) (1996) <- ... <- manager meeting of 'Viessman' in 1994 mailto:sillke@mathematik.uni-bielefeld.de -- Karl Scherer -- (no answer) mailto:karl@kiwi.gen.nz -- Dick Hess -- (ca 1996) mailto:RIHess@compuserve.com -- Math Fun Mailing List -- (no answer) mailto:math-fun@cs.arizona.edu -- Hemme Heinrich -- (May 1998) He is searching for the origin too. mailto:Hemme@FH-Aachen.de -- Martin Gardner -- (July 1998) Hemme Heinrich wrote him, but he didn't know this problem. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - N E W S from rec.puzzles - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - From - Thu Jul 31 14:14:26 1997 Date: Wed, 23 Jul 1997 00:36:55 -0600 From: jimmy_brain@hotmail.com Subject: 4 men crossing a bridge Newsgroups: rec.puzzles Message-ID: <869634267.24673@dejanews.com> Organization: Deja News Posting Service Lines: 28 There are 4 men who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown etc. Each man walks at a different speed. A pair must walk together at a rate of the slower man's pace. Man 1: 1 minute to cross. Man 2: 2 minutes to cross. Man 3: 5 minutes to cross. Man 4: 10 minutes to cross. For example, if Man 1 and Man 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Man 4 returns with the flashlight, a total of 20 minutes have passed, and you have failed the mission. See how quickly you can solve this! p.s. The flashlight cannot shine a long distance. No one can be carried, etc. -------------------==== Posted via Deja News ====----------------------- http://www.dejanews.com/ Search, Read, Post to Usenet From - Thu Jul 31 14:14:58 1997 From: dwboll@gr.hp.com (David Boll) Newsgroups: rec.puzzles Subject: Re: 4 men crossing a bridge Date: 23 Jul 1997 14:44:30 GMT Organization: Hewlett-Packard Co., Greeley, CO, USA Lines: 13 Message-ID: <5r55ce$epd3@hpbs1500.boi.hp.com> References: <869634267.24673@dejanews.com> jimmy_brain@hotmail.com wrote: : There are 4 men who want to cross a bridge. [deleted] Nice puzzle! It is fairly quick, has a bit of a twist, and I hadn't seen it before. Answer: 56,5,78,6,56 or 56,6,78,5,56 <- Subtract 4 from each digit -- Dave Boll Check my homepage: http://www.omn.com/dboll <- new location! Lots of rec math stuff, etc. From - Thu Jul 31 14:16:08 1997 From: Clark Dorman Newsgroups: rec.puzzles Subject: Re: 4 men crossing a bridge Date: 23 Jul 1997 15:18:24 -0400 Organization: PSINet Lines: 62 Message-ID: References: <869634267.24673@dejanews.com> jimmy_brain@hotmail.com writes: > There are 4 men who want to cross a bridge. > They all begin on the same side. > You have 17 minutes to get all of them across to the other side. > It is night. > There is one flashlight. > A maximum of two people can cross at one time. > Any party who crosses, either 1 or 2 people, must have the flashlight with > them. > The flashlight must be walked back and forth, it cannot be thrown etc. > Each man walks at a different speed. > A pair must walk together at a rate of the slower man's pace. > > Man 1: 1 minute to cross. > Man 2: 2 minutes to cross. > Man 3: 5 minutes to cross. > Man 4: 10 minutes to cross. > > For example, if Man 1 and Man 4 walk across first, 10 minutes have > elapsed when they get to the other side of the bridge. If Man 4 > returns with the flashlight, a total of 20 minutes have passed, > and you have failed the mission. > > See how quickly you can solve this! > p.s. The flashlight cannot shine a long distance. No one can > be carried, etc. As it turns out, this puzzle has been discussed a number of times in this newsgroup, and really counts as a FAQ, but it still is not in the archives. Hm...I'm going to complain to the management about this!! Oh, you mean there isn't a "management"? No, no, I'm not volunteering... ... Anyway, what is fascinating about this puzzle is that it is such a "trivial" scheduling problem, and yet remains such a difficult problem. Every time I see this thing, I have to think for 10 minutes before I figure it out. People I pose the question to frequently argue that "it just can't be done" because you have the 10+5+2 minutes for each to get across with the 1 minute person, and another two minutes for the 1 minute person to get back across to get the next. So, "it can't be done", or "there's a trick". SPOILER The solution: Time: Running Total: 1,2 cross: 2 minutes 2 minutes 1 comes back: 1 minute 3 minutes 3,4 cross: 10 minutes 13 minutes 2 comes back: 2 minutes 15 minutes 1,2 cross: 2 minutes 17 minutes And that's it. And the real question: why on earth is this problem so hard?? -- Clark Dorman "Evolution is cleverer than you are." http://cns-web.bu.edu/pub/dorman/D.html -Francis Crick From - Thu Jul 31 14:16:36 1997 From: kll@lns598.lns.cornell.edu (Karen L Lingel) Newsgroups: rec.puzzles Subject: Re: 4 men crossing a bridge Date: 23 Jul 1997 21:11:47 GMT Organization: Wilson Lab, Cornell U., Ithaca, NY 14853 Lines: 19 Distribution: world Message-ID: <5r5s2j$dkd$2@lnsnews.lns.cornell.edu> References: <869634267.24673@dejanews.com> Reply-To: kll@nospam.lns598.lns.cornell.edu In article , Clark Dorman writes: > >And the real question: why on earth is this problem so hard?? > The other real question is: why doesn't the fast guy just bonk the others on the head with the flashlight and then sprint away laughing like this: "bwahh haa haa"? This would be the best solution if we just modify the problem so that the fast guy is a r.p regular, and the other 3 are slow nusgry. Oh, and change the flashlight to a ball peen hammer. -k- -------------------------------------------------------------------------- Karen Lingel, Physicist and Penguinist http://w4.lns.cornell.edu/~kll/ Support the anti-Spam amendment: http://www.cauce.org/ From - Thu Jul 31 14:17:41 1997 From: Eric Robinson Newsgroups: rec.puzzles Subject: Re: 4 men crossing a bridge Date: Wed, 23 Jul 1997 18:02:09 -0700 Organization: University of California, Berkeley Lines: 97 Message-ID: <33D6A991.1AF0@uclink4.berkeley.edu> References: <869634267.24673@dejanews.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit > Anyway, what is fascinating about this puzzle is that it is such a > "trivial" scheduling problem, and yet remains such a difficult > problem. Every time I see this thing, I have to think for 10 minutes > before I figure it out. People I pose the question to frequently > argue that "it just can't be done" because you have the 10+5+2 minutes > for each to get across with the 1 minute person, and another two > minutes for the 1 minute person to get back across to get the next. > So, "it can't be done", or "there's a trick". > And the real question: why on earth is this problem so hard?? I think that our reflex to this type of problem goes something like this: the main difficulty and bottleneck is the flashlight, we need to get it back and forth across the bridge as quickly as possible, therefore the fastest person should always carry the flashlight, therefore Man 1 will accompany each of the other crossers one by one across the bridge, then return with the flashlight. The fallacy of course is in the second step ("we need to get the flashlight across the bridge as quickly as possible"). That is only half the problem, or even less than half, since most of the time is consumed by the slower crossers. The "second half" of the problem is what deserves the most attention, yet we are mislead into focussing on the flashlight because it seems unique and therefore the crux of the problem, when it is not. First stab at a solution to the general problem with two or more crossers and only one light: Group likes with likes: one crosses with two, three crosses with four, five crosses with six, and so on. One and two make solo return trips with the flashlight, then recross again as a pair as many times as neccessary. total number of required transits = 2N - 3 use the pattern: 1,2; 1; 3,4; 2; 1,2; 1; 5,6; 2; 1,2; 1; 7,8; 2; 1,2; 1; . . . If N is odd, terminate the pattern with: 1,N; If N is even, use: M,N; 2; 1,2; where M = N - 1 Total amount of required time: (time required for #1) x (int((N-1)/2) + (time required for #2) x (2 x int(N/2) - 1) + (time required for #4) + (time required for #6) + (time required for #8) + . . . (time required for #N) This will be the fastest possible transit only under certain conditions; I'm having trouble clarifying those conditions. One and Two must be reasonably fast compared to the other crossers, and the even numbered crossers shouldn't be significantly closer in speed to their slower neighbor than their faster neighbor. E.g. the method won't work on the following group: 5 sec 5 sec 5 sec 10 sec 10 sec 15 sec 15 sec 20 sec 20 sec The fastest transit here is: 1,2; 1; 1,3; 1; 4,5; 2; 6,7; 3; 1,2, 1; 1,3; 1; 8,9; 2; 1,2; From - Thu Jul 31 14:20:13 1997 From: mwdaly@kodak.com (Matthew Daly) Newsgroups: rec.puzzles Subject: Re: 4 men crossing a bridge Date: Mon, 28 Jul 1997 14:07:55 GMT Organization: Eastman Kodak Company Lines: 56 Message-ID: <33df9f81.1017958109@newsserver.rdcs.kodak.com> References: <869634267.24673@dejanews.com> Reply-To: mwdaly@kodak.com (Matthew Daly) Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Clark Dorman , if that is your REAL name, said: >As it turns out, this puzzle has been discussed a number of times in >this newsgroup, and really counts as a FAQ, but it still is not in the >archives. Hm...I'm going to complain to the management about this!! >Oh, you mean there isn't a "management"? No, no, I'm not >volunteering... ... *giggle* I'll make a point of checking Deja News and seeing how many times this has been posted in the past year and see if its annoyance factor merits FAQ inclusion. I can say with a fair amount of confidence that it will be included in the next incarnation of the archives, but coming out with that is a pretty Herculean task. (Personally, I think that it's a Syssiphean task, but it's Chris Cole's burden and not mine.... :-) Actually, there are a number of very clever and oft-posted puzzles that just weren't widely distributed before the most recent revision of the archive. The three that I can think of are: 1) The four men crossing a bridge with a lantern 2) The three light bulbs with switches in a different room (seen elsewhere in the current feed) 3) The voting pirates distributing a treasure of gold pieces. Since the last one is one that I like a lot and I really haven't seen it that often lately, here it is again. (If this is repetition, at least this phrasing of the problem might have the most complete set of assumptions posted to date.) Ten pirates come across a treasure of 100 gold pieces. As captain, it is your job to distribute the gold among yourself, your first mate, second mate, and so on down to your ninth mate you run a well-ranked heirarchical ship). However, your distribution will be voted on by all pirates (including you), and if your plan does not receive a majority (i.e. MORE than 50%), then there will be a mutiny and you will be put to death. Then everyone will be promoted one spot and your first mate will propose his own distribution scheme. This pattern of suggesting a distribution, voting, mutiny, death, and promotion will continue until a plan receives more than 50% of the vote. All the pirates are completely rational, perfect logicians, and are civil as well (that is, if they can get the same amount of gold with or without death, then they will prefer not to kill). As the captain, your first priority is to survive and your second priority is to keep as much gold as possible. What distribution do you suggest? -Matthew -- Matthew Daly I feel that if a person has problems communicating mwdaly@kodak.com the very least he can do is to shut up - Tom Lehrer My opinions are not necessarily those of my employer, of course. --- Support the anti-Spam amendment! Join at http://www.cauce.org --- From - Thu Jul 31 14:35:56 1997 From: ftww@staff.cs.su.oz.au (Geoff Bailey) Newsgroups: rec.puzzles Subject: Voting Pirates (WAS: Re: 4 men crossing a bridge) Followup-To: rec.puzzles Date: 29 Jul 1997 11:18:28 +1000 Organization: Thermonuclear Toys, Pty Ltd Lines: 142 Sender: ftww@cs.su.oz.au (Fred the Wonder Worm) Message-ID: <5rjgd4$df1@staff.cs.su.oz.au> References: <869634267.24673@dejanews.com> <33df9f81.1017958109@newsserver.rdcs.kodak.com> Reply-To: ftww@cs.su.oz.au (Fred the Wonder Worm) In article <33df9f81.1017958109@newsserver.rdcs.kodak.com>, Matthew Daly wrote: > >Actually, there are a number of very clever and oft-posted puzzles that >just weren't widely distributed before the most recent revision of the >archive. The three that I can think of are: [ ... ] >3) The voting pirates distributing a treasure of gold pieces. > >Since the last one is one that I like a lot and I really haven't seen it >that often lately, here it is again. (If this is repetition, at least this >phrasing of the problem might have the most complete set of assumptions >posted to date.) > >Ten pirates come across a treasure of 100 gold pieces. As captain, it is >your job to distribute the gold among yourself, your first mate, second >mate, and so on down to your ninth mate you run a well-ranked heirarchical >ship). However, your distribution will be voted on by all pirates >(including you), and if your plan does not receive a majority (i.e. MORE >than 50%), then there will be a mutiny and you will be put to death. Then >everyone will be promoted one spot and your first mate will propose his own >distribution scheme. This pattern of suggesting a distribution, voting, >mutiny, death, and promotion will continue until a plan receives more than >50% of the vote. > >All the pirates are completely rational, perfect logicians, and are civil >as well (that is, if they can get the same amount of gold with or without >death, then they will prefer not to kill). As the captain, your first >priority is to survive and your second priority is to keep as much gold as >possible. What distribution do you suggest? SPOILER AHEAD: This version seems to be trivial (although perhaps counter-intuitive). The captain gets to keep all of the gold (maybe this is realistic). Reasoning backwards: If there is one pirate, he gets to keep all the gold (100% vote). If there are two pirates, each has only a 50% vote. The first one must give all his gold to the second if he wants to live. If there are three pirates, the first keeps all the gold, and the second agrees with this since he is not worse off. If there are n > 3 pirates, the first keeps all the gold and the last n-2 agree since they are not worse off. This can be sort of summarized in the following table (the higher the number of the pirate, the higher he is in the hierarchy): payoff per pirate 10 9 8 7 6 5 4 3 2 1 1 100 # 2 0 100 p 3 100 0 0 i 4 100 0 0 0 r 5 100 0 0 0 0 a 6 100 0 0 0 0 0 t 7 100 0 0 0 0 0 0 e 8 100 0 0 0 0 0 0 0 s 9 100 0 0 0 0 0 0 0 0 10 100 0 0 0 0 0 0 0 0 0 More interesting things happen if we assume that the pirates may kill if they are not better off (assuming they don't get all the gold). This encourages the higher ranks to toss a few coins to the lower ranks so they don't mutiny. The payoff matrix starts off like this: payoff per pirate 10 9 8 7 6 5 4 3 2 1 # p 1 100 i 2 0 100 r 3 99 1 0 a 4 97 0 2 1 t 5 97 0 1 0 2 e 6 96 0 1 2 1 0 s 7 But now there are two choices for 7: 7 96 0 1 2 0 0 1 7 96 0 1 0 0 2 1 and the best choice for 8 depends on which of these would be chosen. If it were the first option, then either of the following would do: 8 95 0 1 0 0 1 1 2 8 95 0 1 2 0 1 1 0 Otherwise, one of these two: 8 95 0 1 0 1 1 0 2 8 95 0 1 2 1 1 0 0 To be safe, then, the eighth pirate should ensure that 4 of the remaining seven would be better off no matter which choice 7 makes. The best such payoff is: 8 94 0 1 0 2 1 2 0 Now again 9 has two equally good choices: 9 95 0 1 2 1 0 0 0 1 9 95 0 1 0 1 0 2 0 1 And so to be safe 10 should choose: 10 91 0 1 2 0 2 1 0 1 2 Payoff matrix: payoff per pirate 10 9 8 7 6 5 4 3 2 1 1 100 # 2 0 100 p 3 99 1 0 i 4 97 0 2 1 r 5 97 0 1 0 2 a 6 96 0 1 2 1 0 t 7 96 0 1 2 0 0 1 or e 7 96 0 1 0 0 2 1 s 8 94 0 1 0 2 1 2 0 9 95 0 1 2 1 0 0 0 1 or 9 95 0 1 0 1 0 2 0 1 10 91 0 1 2 0 2 1 0 1 2 Cheers, Geoff. ------------------------------------------------------------------------------- Geoff Bailey (Fred the Wonder Worm) | Programmer by trade -- ftww@cs.su.oz.au | Gameplayer by vocation. ------------------------------------------------------------------------------- From - Wed Aug 6 14:26:51 1997 From: "Terry & Fiona CRACKETT" Newsgroups: rec.puzzles Subject: Microsoft Bridge Puzzle Date: 4 Aug 1997 11:52:22 GMT Organization: OzEmail Ltd - Australia Lines: 44 Message-ID: <01bca0cc$f0e14940$b0d06ccb@dialup.ozemail.com.au> I was sent the following which I would love an answer for: Subject: FW: A puzzle given to Microsoft staff A Microsoft entry question! Bill Gates gives to all employees, can you solve it. Note: Microsoft expects you to answer this question in under 5 minutes! Notes: There is not a trick behind how to accomplish this. It is the simple movement of resources in the appropriate order issue. There are two known answers to this problem. This is based on a question Microsoft gives to all prospective employees. Puzzle: All of "U2" need to cross a bridge. (Their concert starts in 17 minutes). All four men begin on the same side of the bridge. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each band member walks at a different speed. A pair must walk together at the rate of the slower mans pace. Bono: 1 minute to cross Edge: 2 minutes to cross Adam: 5 minutes to cross Larry: 10 minutes to cross For example: If Bono and Larry walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Larry then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. Cheers From - Wed Aug 6 14:29:24 1997 From: mwdaly@kodak.com (Matthew Daly) Newsgroups: rec.puzzles Subject: Re: Microsoft Bridge Puzzle Date: Tue, 05 Aug 1997 21:59:33 GMT Organization: Eastman Kodak Company Lines: 44 Message-ID: <33eba1a0.442156625@newsserver.rdcs.kodak.com> References: <01bca0cc$f0e14940$b0d06ccb@dialup.ozemail.com.au> <33E73325.69A1@pms622.pd9.ford.com> <33E78053.EBAE7EBE@mitre.org> Reply-To: mwdaly@kodak.com (Matthew Daly) Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Tim Monaghan , if that is your REAL name, said: >jscharf1 wrote: > >> here's my solution: >> >> Larry & Bono = 10 min >> Bono = 1 min >> Edge & Adam = 5 min >> -------- >> Total 16 min >> >> They all crossed the bridge and under 17 min > >Two problems with your solution. First, They have not all crossed. >Your second step, "Bono = 1 min" clearly implies that he returns to the >starting side of the bridge and remains there since he is not included >in the remaining trip. So you have three on one side and one on the >other. Second, by rule, the flashlight has been carried to the other >side of the bridge in step three. As a result, you have Larry, Edge, >Adam, AND the flashlight on one side, and Bono on the other. There is >only one minute left, and the fastest available carrier of the >flashlight will take 2 minutes just to get back across the bridge! You >run out of time before the last trip can even begin. You are, however, >close to the right answer. I thought that the answer posted was delightful. The question demanded that everyone cross the bridge, and this solution has everyone crossing the bridge. In fact, Bono crossed it twice! :-) If Bill Gates intended for all four band members to be on the far side of the bridge at the end of the 17 minutes, then he should have said THAT. I only hope that jscharf1 doesn't get hired by Microsoft to interpret functional specs for upcoming software projects.... -Matthew -- Matthew Daly I feel that if a person has problems communicating mwdaly@kodak.com the very least he can do is to shut up - Tom Lehrer My opinions are not necessarily those of my employer, of course. --- Support the anti-Spam amendment! Join at http://www.cauce.org --- From - Thu Aug 7 12:52:03 1997 From: kll@nospamlns598.lns.cornell.edu (Karen L Lingel) Newsgroups: rec.puzzles Subject: Re: Microsoft Bridge Puzzle Date: 4 Aug 1997 18:31:29 GMT Organization: Wilson Lab, Cornell U., Ithaca, NY 14853 Lines: 49 Distribution: world Message-ID: <5s5761$skm$1@lnsnews.lns.cornell.edu> References: <01bca0cc$f0e14940$b0d06ccb@dialup.ozemail.com.au> Reply-To: kll@nospam.lns598.lns.cornell.edu In article <01bca0cc$f0e14940$b0d06ccb@dialup.ozemail.com.au>, "Terry & Fiona CRACKETT" writes: >I was sent the following which I would love an answer for: > >Subject: FW: A puzzle given to Microsoft staff > >A Microsoft entry question! Bill Gates gives to all employees, >can you solve it. > >Note: Microsoft expects you to answer this question in under 5 minutes! > >Notes: There is not a trick behind how to accomplish this. It is the >simple movement of resources in the appropriate order issue. There >are two known answers to this problem. This is based on a question >Microsoft gives to all prospective employees. > >Puzzle: > >All of "U2" need to cross a bridge. (Their concert starts in 17 >minutes). [yada yada yada] This *is* a trick puzzle. Bill wants to see if his employee prospects READ THE FAQ before posting a tired old oft-posted hoary chestnut that has been posted within the LAST WEEK for crying out loud. I guess you'll be working for Burger King. ObPuzzle1: Why do so many companies use tired worn puzzles which any rec.puzzles reader knows backwards and forwards and can "solve" in WAY fewer than 5 minutes? No Particle Physics employers do this. They ask actual physics questions. Revolutionary, huh? Of course, rec.puzzles regulars are smarter and more attractive than other people; perhaps that is why they are in such demand at Microsoft. ObPuzzle2: Why don't they put crossword puzzles on the GRE or SAT? ObPuzzle3: Would you go to a doctor or lawyer whose board exam consisted only of rec.puzzles FAQs? -k- -------------------------------------------------------------------------- Karen Lingel, Physicist and Penguinist http://w4.lns.cornell.edu/~kll/ Support the anti-Spam amendment: http://www.cauce.org/ From - Sat Aug 16 21:39:51 1997 From: ncbst@vms.cis.pitt.edu Newsgroups: rec.puzzles Subject: HELP PLEASE! On bridge crossing problem.... Date: 15 Aug 97 13:24:59 EDT Organization: University of Pittsburgh Lines: 39 Message-ID: <5t23ds$cgm@usenet.srv.cis.pitt.edu> Hi all, I wanted to get input on the following problem (if possible solutions would be greatly appreciated). Thanks! Cathy ******************************************************************************** "U2" HAVE A CONCERT THAT STARTS IN 17 MINUTES AND THEY MUST ALL CROSS A BRIDGE TO GET THERE. ALL FOUR MEN BEGIN ON THE SAME SIDE OF THE BRIDGE. YOU MUST HELP THEM ACROSS TO THE OTHER SIDE. IT IS NIGHT. THERE IS ONE FLASHLIGHT. A MAXIMUM OF TWO PEOPLE CAN CROSS AT ONE TIME. ANY PARTY WHO CROSSES, EITHER 1 OR 2 PEOPLE, MUST HAVE THE FLASHLIGHT WITH THEM. THE FLASHLIGHT MUST BE WALKED BACK AND FORTH, IT CAN NOT BE THROWN, ETC. EACH BAND MEMBER WALKS AT A DIFFERENT SPEED. A PAIR MUST WALK TOGETHER AT THE RATE OF THE SLOWER MAN'S PACE: BONO: 1 MINUTE TO CROSS EDGE: 2 MINUTES TO CROSS ADAM: 5 MINUTES TO CROSS LARRY: 10 MINUTES TO CROSS FOR EXAMPLE: IF BONO AND LARRY WALK ACROSS FIRST, 10 MINUTES HAVE ELAPSED WHEN THEY GET TO THE OTHER SIDE OF THE BRIDGE. IF LARRY THEN RETURN WITH THE FLASHLIGHT, A TOTAL OF 20 MINUTES HAVE PASSES AND YOU HAVE FAILED THE MISSION. NOTES: THERE IS NO TRICK BEHIND THIS. IT IS THE SIMPLE MOVEMENT OF RESOURCES IN THE APPROPRIATE ORDER. THERE ARE TWO KNOWN ANSWERS TO THIS PROBLEM. ******************************************************************************** From - Thu Aug 21 18:31:09 1997 From: mwdaly@kodak.com (Matthew Daly) Newsgroups: rec.puzzles Subject: FAQ change Date: Wed, 20 Aug 1997 15:22:12 GMT Organization: Eastman Kodak Company Lines: 37 Message-ID: <33ff09c8.431831062@newsserver.rdcs.kodak.com> Reply-To: mwdaly@kodak.com (Matthew Daly) Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Well, after a deluge of comments (well, two actually), I was convinced to put the "four men with a lantern crossing the bridge" puzzle into section 2 of the FAQ. Since I never manage to write a cook-free version the first time out, I figured I would put my prose out here ahead of time for people to bash on ahead of time. ---- 2.6. Four men are on one side of a rickety bridge on a dark night. The bridge is only strong enough to support two men at a time. It is also necessary for the men crossing the bridge to carry a lantern to guide their way, and the four men have only one lantern between them. Andy can cross the bridge in 1 minute, Ben in 2, Charlie in 5, and Dan in ten minutes. How quickly can all four men be together at the other side? The solution is surprising to some people because they initially suspect that it is fastest if Andy escorts everyone across because he can return the fastest. However, a faster method requires only 17 minutes. First, Andy and Ben cross (2 min), then Andy returns (1 min). Then, Charlie and Dan cross (10 min) and Ben returns (2 min). Finally, Andy and Ben recross (2 min). In short, you save two minutes by having the two slowest people cross the bridge in the same trip. ---- Clear? Concise? Correct? -Matthew -- Matthew Daly I feel that if a person has problems communicating mwdaly@kodak.com the very least he can do is to shut up - Tom Lehrer My opinions are not necessarily those of my employer, of course. --- Support the anti-Spam amendment! Join at http://www.cauce.org --- ------------------------------------------------------------------------------- From - Mon Sep 15 13:36:01 1997 From: Wolfram Kresse Newsgroups: rec.puzzles,alt.brain.teasers Subject: family on a bridge Date: Sun, 14 Sep 1997 22:50:52 +0200 Organization: Fraunhofer-IGD, Germany. Currently: University of Cape Town, South Africa Message-ID: <341C4E2C.167E@mindless.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 43 Hi. Another oldie-but-goodie: Bridge. Midnight. New moon. Overcast. 4 people have to cross the bridge: Child, Father, Uncle, Grandpa. All they have is a single flashlight and for some reason they know that the batteries will last for exactly 60 minutes. The bridge can carry only two persons at a time - strange enough, it depends only on the *number*, not on the *weight* of the people... ;-) However, each person takes a different amount of time to cross the bridge: Child: 5 min Father: 10 min Uncle: 20 min Grandpa: 25 min In what order do they have to cross the bridge so that nobody is on the bridge in the dark - *and* the flashlight doesn't burn out before they all reached the other side? ...oh yes, I forgot to mention: it is also quite foggy, the beam of the flashlight cannot be seen for more than a few meters - the bridge is far longer. Cheers, Wolfram -- +-------+-----Wolfram Kresse---------------------------------------------+ wkresse@igd.fhg.de http://www.igd.fhg.de/~wkresse --------------------------------------------------------------------------