Five People, One Torch
The puzzle
Five people must cross a rickety bridge at night. It holds two at a time, and the single torch must be carried on every crossing. A pair crosses at the slower one's pace.
Their individual times are 1, 2, 5, 10 and 15 minutes. What is the fastest everyone can be across?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
The obvious plan - the fastest person escorts everyone, one at a time - costs 1 + 15 + 1 + 10 + 1 + 5 + 2 = 35 minutes. Beat it.
Hint 2
Two slow people crossing together pay the slower time once instead of twice. Sending 10 and 15 over as a pair costs 15 rather than 25.
Show the answer Hide the answer
28 minutes, by pairing the two slowest and letting the two fastest do the ferrying.
How to get there
Send 1 and 2 across (2 min). Send 1 back (1). Send 10 and 15 across together (15) - this is the move that pays for itself, since 15 covers both of them. Send 2 back (2).
Now 1, 2 and 5 are on the near side with the torch and 10 and 15 are done. Send 1 and 2 across (2), send 1 back (1), send 1 and 5 across (5).
Total: 2 + 1 + 15 + 2 + 2 + 1 + 5 = 28 minutes. The general rule for sorted times is to compare two moves at each stage - the fastest walker escorting the slowest, costing t1 + tn, against the two slowest crossing together, costing 2*t2 + t1 + tn. Here 2 + 1 + 15 + 2 = 20 beats 1 + 15 twice over, so the pairing wins.
The technique worth keeping
When a group pays the cost of its worst member, put the two worst members in the same group. The two fastest then act as couriers, and the saving is the second-slowest time, charged once rather than twice.