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.
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.
Question
Guest
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.
Link to comment
Share on other sites
1 answer to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.