Crossing the Bridge

Date: 05/12/97 at 19:27:58
From: Ian Comfort
Subject: 4 men want to cross a bridge...

One of my friends gave me this problem.  Try as I might, I cannot seem 
to get the answer he says he does.  Well, here goes:

Four men want to cross a bridge.  The bridge is of a width such that a 
maximum of 2 people may cross at a time.  

One man takes 10 minutes to cross, another takes 5 minutes to cross,
another takes 2 minutes to cross, and the last takes 1 minute to 
cross.

I will call these men A, B, C, and D, respectively.

Here is the catch.  If two people cross the bridge together, they must 
walk at the pace of the slower one. So if A and B cross, they take 10 
minutes. Also, it is night. Each trip requires a flashlight.  There 
is only one flashlight. The men are not allowed to toss the light over 
the river.

How fast can you get all 4 men over the bridge?

Here is what I have done:

I figured that there must be 5 total trips. Two go across, one comes 
back with the light, two more go, one comes back again, and then the 
last two men cross with the light.

I also figured that it would be fastest to have D make all the return 
trips, so I came up with something like this:

   A and D go across               10 minutes
   D goes back with light           1 minute
   B and D go across                5 minutes
   D goes back with light           1 minute
   C and D go across                2 minutes
   --------------------          ---------------
   Total                           19 minutes

My friend says he can get them across in 17 minutes, but he won't tell 
me how. Please help!

Ian Comfort

Date: 05/23/97 at 15:23:24
From: Doctor Barney
Subject: Re: 4 men want to cross a bridge...Rev. 1

Hi Ian,

This is a cool problem. First I read the problem and tried to solve 
it before I read your answer. I came up with the same solution. But 
then, as I thought about it longer, I did find a way to get all four 
men across the bridge with the restrictions imposed in 17 minutes, no 
tricks.  

Here's a hint: You are correct that because of the flashlight there 
will be three trips across the bridge with two people together, and 
two trips back with light with one person bringing the light back 
alone.  Now, instead of optimizing the back with light trips, see if 
you can optimize the across trips to create a better overall solution, 
even if one of the return trips takes longer than 1 minute.   

-Doctor Barney,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 02/10/98 at 05:33:06
From: Nigel Armitage
Subject: Bridge riddle

Dr. Math,

Can you tell me the answer to this one please?

There are 4 men on one side of a narrow bridge.  At most 2 men can 
cross at a time, and since it is night and the bridge is narrow and 
rickety, they must cross with a flashlight. Unfortunately there is 
only 1 flashlight, and all 4 must get across the bridge in at most 
17 minutes.

However, the men take the following lengths of time to cross the 
bridge: 

Man No. 1 takes 1 minute
Man No. 2 takes 2 minutes
Man No. 3 takes 5 minutes
Man No. 4 takes 10 minutes

When two men walk together, they walk at the pace of the slower one.  
So if No. 1 and No. 4 cross together, it will take them 10 minutes.

How can they do it and all 4 get across in no more than 17 minutes?

Best wishes.

Nigel Armitage
Link (Legal Information Network), UK

Date: 02/10/98 at 06:55:06
From: Doctor Allan
Subject: Re: Bridge riddle

Hello Nigel,

First of all I hope that you agree with me that there must be a total 
of 5 trips. First two go across, then one returns with the flashlight, 
then two more go across, one returns with the flashlight, and finally 
the two remaining men go across.

Now if you optimize the trips where the flashlight is returned, you 
will get something like this:

No. 1 and No. 4 go across:   10 minutes
No. 1 returns with flash:     1 minute
No. 1 and No. 3 go across:    5 minutes
No. 1 returns with flash:     1 minute
No. 1 and No. 2 go across:    2 minutes
                             ----------
                             19 minutes

This is the first solution one tries (at least I did!). Probably one 
should try to optimize the across trips instead of the trips returning 
with the flashlight in order to get a better result.      

I will give you a hint:

No. 1 and No. 2 go across:    2 minutes
No. 2 returns with flash:     2 minutes
No. 3 and No. 4 go across:   10 minutes
                             ----------
                             14 minutes

Now No. 1, No. 3 and No. 4 have crossed, so one of these needs to return 
with the flashlight and afterwards go across with No. 2 in 3 minutes - 
do you see how?

-Doctor Allan,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/