Five People, One Torch

  • Medium
  • River crossing puzzles
  • Tests: Pairing the slow walkers instead of escorting them

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.