Four people A, B, C and D come to a river at night, and they must cross the river to reach the other side. The only way to cross the river is using a fragile bridge that can withstand the weight of only two people at a time. They have one torch and, because it's night, the torch has to be used when crossing the bridge. Person A can cross the bridge in one minute, B in two minutes, C in five minutes, and D in eight minutes. When two people cross the bridge together, they must move at the slower person's pace. How can they cross the bridge in 15 minutes?
Solution:
Initially {A,B,C,D} {}
Step 1: A and B cross the bridge 2 minutes {C,D} {A,B}
Step 2: A returns to the original side 1 minute {A,C,D} {B}
Step 3: C and D cross the bridge 8 minutes {A} {B,C,D}
Step 4: B returns to the original side 2 minutes {A,B} {C,D}
Step 5: A and B cross the bridge 2 minutes {} {A,B,C,D}
After 5 steps everyone has crossed the river. Total time taken = 2+1+8+2+2 = 15 minutes!!