Four people, one torch
Four people must cross a narrow bridge at night. They have one torch, which must be carried on every crossing, and at most two people can be on the bridge at once. Alone, they take 1, 2, 5 and 8 minutes to cross; two people crossing together walk at the slower one's pace.
What is the shortest total time, in minutes, for all four to get across?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
The obvious plan, in which the fastest person walks each of the others across and comes back with the torch, takes 17 minutes. Where does it waste time?
Send the two slowest across together, so that you only pay for the 8 once and the 5 is hidden behind it.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. The two slowest people should cross together, so that the 5 costs nothing extra. For that to work, someone fast must already be on the far side to bring the torch back.
The plan.
- 1 and 2 cross: 2 minutes.
- 1 comes back: 1 minute.
- 5 and 8 cross: 8 minutes.
- 2 comes back: 2 minutes.
- 1 and 2 cross: 2 minutes.
Total: minutes.
Why not less. Take the simplest kind of plan: three trips across and two back. If 5 and 8 cross on different trips, those two trips already cost , and the three other trips cost at least 1 each, so at least 16. If they cross together, it cannot be on the first trip (one of them would have to bring the torch back) nor on the last (only two people can be left for it). So it is the middle trip, and the torch comes back once before it and once after it, carried by two different people who crossed on the first trip. The first trip, the two returns and the last trip then cost at least , for a total of at least 15. Plans with more trips are longer still; a computer search over all plans confirms that 15 is the minimum.
The trap. Escorting everyone with the fastest person costs . With times 1, 2, 5, 10 both plans give 17; here, pairing the slow ones saves 2 minutes.