Topic: Cross the river
 Message: Posted by: Steve Martin (Mar 8, 2006 02:22PM)
Here is a nice puzzle, which foxed me for ages:

Adam, Bill, Chris and Dave are on one side of a bridge over a river at night.

Each of them is able to walk at different speeds.

Adam is the fastest - it takes him 1 minute to cross the bridge.
Bill is the next-fastest - it takes him 2 minutes to cross the bridge.
Chris is the next-fastest - it takes him 5 minutes to cross the bridge.
Dave is the slowest - it takes him 10 minutes to cross the bridge.

They have one torch between them, and this must be carried on the bridge at all times. It cannot be thrown across the river.

They must cross no more than two at a time, travelling at the speed of the slower person.

What must they do for all of them to arrive on the other side of the river in no more than 17 minutes?
 Message: Posted by: TomasB (Mar 8, 2006 02:27PM)
I found two slightly different solutions.

/Tomas
 Message: Posted by: Steve Martin (Mar 8, 2006 02:31PM)
Yes - that's right. There are two.
 Message: Posted by: 0pus (Mar 8, 2006 02:31PM)
I agree with Tomas.

(He's an ace at these.)
 Message: Posted by: stanalger (Mar 8, 2006 03:06PM)
The two differ only in the second and fourth (return-the-torch-to-the-others)
crossings.
 Message: Posted by: 0pus (Mar 8, 2006 03:57PM)
Now you are giving too much away. ;)
 Message: Posted by: mike paris (Mar 17, 2006 11:05AM)
Allowing for the return trips , I still arrive at 19 minutes
+1 return
+i return
total 19.
unless there is a rope for him to swing back on, who is going to volunteer the answer.
 Message: Posted by: Jonathan Townsend (Mar 17, 2006 11:18AM)
Is there something more efficient than setting up a table or tree search for doing this class of problem?

On the "real world" type side of this puzzle...
Let me get this right... One has a motercycle with sidecar, one has a nice italian sportscar and at least one has has a tandem bicycle. And the bike easily fits on the back of the car... and none of them have a cellphone that works. Presuming none of them are birds or bats of course. ;)
 Message: Posted by: TomasB (Mar 17, 2006 12:21PM)
Mike, you are wasting too much time by not letting the slowest pair walk together. So the reasoning would be that if you can't move a slow one across very fast, you might as well get another slow person over at the same time to be done with him also and not waste time on him later.

And I think that answers Jonathan's question also. Once you get the idea just mentioned there's really only two ways to do it and both ways will end up taking the same amount of time. So no exhaustive search is neccesary since you can reason your way to the solution.

/Tomas
 Message: Posted by: mike paris (Mar 18, 2006 08:15AM)
Thomas,if the 2 slowest go across together dave 10 and chris 5, it will still take chris 5 minutes more to return across the bridge with the torch, that's 15 minutes already used,there are still 3 more people to cross and return? so it still don,t make sense .(to me)
 Message: Posted by: TomasB (Mar 18, 2006 08:34AM)
Mike, once the slowest pair have walked across there can be a fast one already there to bring the torch back.

/Tomas
 Message: Posted by: mike paris (Mar 18, 2006 09:14AM)
Ok ,got it, thanks,see what I mean about some easy ones are hard.(they are ALL easy when you know) he he.
 Message: Posted by: Steve Martin (Mar 18, 2006 09:27AM)
When I first heard this puzzle it took me AGES to find the solution. After many attempts I first concluded it was impossible. It's easy when you know how, of course!