1 reply to this topic

[bole]

This is an interesting puzzle. Very few people (including some mathematicians) that I've pitched the puzzle to have been able to solve it. But once you know the solution, you wonder why you couldn't solve it earlier. The solution points to an important property in scheduling problems.

The puzzle:

There is a bridge over a river that is going to blow up in 17 minutes. Four people want to cross the bridge in time before it blows up. Each person has different physical ailments and thus takes different times to cross the bridge.

Crossing constraints:
Further, it is dark and since they have only one flashlight, they must cross the bridge as follows: two persons cross the bridge, and one comes back with the flashlight, then two more persons cross the bridge and one comes back and so on until all four are across the bridge.

Each of the four persons take the following times to cross the bridge one way:
A: 10 minutes
B: 5 minutes
C: 2 minutes
D: 1 minute

When two persons cross the bridge, the time it takes is equal to the time it takes the slower person to cross. For example, if A and C cross together, it will take them 10 minutes to cross but if B and D cross it takes 5 minutes.

For example, if A and D first cross the bridge first and D comes back with the flashlight, then it takes a total of 10 + 1 = 11 minutes.

The question is: how would you schedule the bridge crossings so that all four can cross the bridge given the crossing constraints within 17 or less minutes.

Spoiler for Solution

The solution is as follows:
C and D first cross and D comes back = 3 minutes (C is on the other side)
A and B then cross and C comes back = 12 minutes (A, B are on the other side)
C and D finally cross = 2 minutes (A, B, C and D are on the other side)
------------------
Total = 17 minutes

The useful property from the view of scheduling is that we want slow tasks to occur in parallel so that time can be saved. Most people try to always use D to make the trip back after each crossing, but this means that A and B would never cross the bridge together.

[Martini]

Welcome to the site, bole. This riddle was posted already here by one of our most excellent members. Any further discussion regarding this riddle can be had in that thread.

Tip: Posting the solution in the OP takes a little away from the discussion on how to solve the riddle. It can always be provided in a later post if no one seems to be getting it. Just a suggestion.

this thread is locked