The Four travelers

[AngelFish]

Four travelers, Mr. A, B, C, and D, have to cross a bridge over a deep ravine. It 's a very dark night and the they have only an old fashioned oil lamp for light. The light is essential for successfully crossing the ravine because the bridge is very old and has a lot of holes and loose boards. Even worse, its construction is really quite weak, and in its dilapidated condition, it can only support two of the men at a time. They are also out of cell phone range and are so unable to call for help. If two men cross the bridge together, the time for them to cross is equal to the crossing time of the slower man because the faster man must help the other along.


How should the men arrange themselves to cross the bridge in the fastest possible time?

Mr. A takes 1 minute to cross the bridge.
Mr. B takes 2 minutes to cross.
Mr. C takes 5 minutes to cross.
Mr. D is recovering from surgery and takes 10 minutes to cross.


Example (not the best solution):

A and D cross first, taking 10 minutes to cross.
A returns with the light, taking another 1 minute.
B and C cross, taking 5 minutes.
B returns with the light in 2 minutes.
A and B cross, taking 2 more minutes.
Total time = 10+1+5+2+2 = 20 Minutes.

It took me about 5 minutes to solve this problem. How long did it take you?

[Ashbad]

A, D over, 10
A back, 1
A, C over, 5
A back, 1
A, B over, 2

Total, 19

Optimized one cycle

[AngelFish]

That's still not the optimal solution

[Ashbad]

Really?  O.o. All I did for mine is make A cross over with the light instead of B on the second pass, saves 1 minute.  I wonder what it is

[Quigibo]

From a game theory perspective, I'd have to agree that 19 is the minimum amount of time it can take unless there is something fundamental about this problem that I'm not understanding (which I assume there is).

-Each trip across must be a full trip due to the 3 person rule.  Otherwise it could only increase the time.
-Mr. A has to travel with every person or else it could only increase time.
-I'm assuming you can't "toss" the lamp over the bridge, set it on fire, or cut it and swing to the other side.

[leafy]

I saw this problem, and I remember it was either 15 or 17 for the optimal solution. I'll try working it out again ^^

[AngelFish]

From a game theory perspective, I'd have to agree that 19 is the minimum amount of time it can take unless there is something fundamental about this problem that I'm not understanding (which I assume there is).

-Each trip across must be a full trip due to the 3 person rule.  Otherwise it could only increase the time.

Going forwards across the bridge, yes. One person must necessarily travel back across the bridge to bring the lamp back to the others. But I assure you that 19 is *not* the minimum time required and I also highly recommend not using Google for the answer.

[Builderboy]

17 is the optimal solution and let me assure you the solution does not involve anything tricky like leaving members in the middle of the bridge or anything

[Juju]

Hmmm... It's kinda hard.

[AngelFish]

17 is the optimal solution and let me assure you the solution does not involve anything tricky like leaving members in the middle of the bridge or anything

Yep

EDIT: My Linux automatically threw this link into this post, so enjoy  http://community.linuxmint.com/

[Hayleia]

AB     2    →
B       2    ←
CD     10  →
A       1   ←
AB      2   →
Total 17

[AngelFish]

Bingo.

[Hayleia]

Do I explain or do you (or do anyone else do) ?
EDIT: I think I'll explain, so.
Well, the only thing is to make C and D cross the bridge together, only one time.
So, AB have to go first, then A or B comes back to give the lamp to C and D so they can cross the bridge and give the lamp to A or B (the one who stayed) so he goes back to look for the last one.
In fact, C can even be slower, his travelling time doesn't count as it is absorbed by D.

I also highly recommend not using Google for the answer.

All I found on Google was the question... (°-.-)