The problem
Four people must cross a bridge at night. They have one torch, the bridge holds at most two at a time, and anyone crossing must carry the torch. Crossing times are 1, 2, 5 and 10 minutes; a pair moves at the slower person's pace.
Get everyone across in 17 minutes.
The greedy attempt
The obvious idea is to let the fastest person shuttle the torch back each time:
1 and 2 cross (2), 1 returns (1), 1 and 5 cross (5), 1 returns (1), 1 and 10 cross (10). Total: 19 minutes.
This feels efficient and is wrong.
The optimal solution
The insight: 10 and 5 should cross together, so that the 5-minute crossing costs nothing extra - it happens underneath the 10.
- 1 and 2 cross. (2)
- 1 returns. (1)
- 5 and 10 cross. (10)
- 2 returns. (2)
- 1 and 2 cross. (2)
Total: 17 minutes.
Notice the fastest person is not the one who returns the second time. That is the counter-intuitive move.
Why greedy fails
A pair's cost is the maximum of the two times, not the sum. So pairing two slow people wastes only the difference between them, while pairing a slow person with a fast one wastes the fast person's entire trip.
Whenever a cost function is a max rather than a sum, greedy shuttling is usually suboptimal - that is the transferable lesson.
The general rule
Sort the times. Repeatedly move the two slowest across using whichever is cheaper:
- Pattern A: fastest escorts each slow person separately - costs t1 + 2 t2 ... in the shuttle form.
- Pattern B: two fastest cross, fastest returns, two slowest cross together, second-fastest returns.
Compare 2 t2 + t_n + t1 against t2 + 2 t1 + t_n at each step and take the smaller. For 1, 2, 5, 10 that comparison picks pattern B, giving 17.
What is tested
Recognising that an obvious local rule is not globally optimal, and being willing to check rather than assume. That is worth more than the specific answer.
More in brainteasers.