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:
- Om bij te lichten moet er steeds een zaklamp mee;
- Er kunnnen niet meer dan twee personen tegelijkertijd oversteken;
- Niet alle personen zijn even snel: de zanger doet 1 minuut over de
oversteek, de gitarist 2 minuten, de bassist 5 minuten en de drummer
10 minuten;
- Wanneer twee personenen tegelijkertijd oversteken, dan hebben ze
samen de snelheid van de langzaamste.
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
--------------------------------------------------------------------------