The Bridge at Night

Question

Four people must cross a bridge at night with one flashlight. At most two can cross at a time, and any crossing party must carry the flashlight (so someone must walk it back). Their individual crossing times are 1, 2, 5, and 10 minutes; a pair moves at the slower person's pace. What is the minimum total time for all four to cross?

Accepted Answer

17 minutes. The insight: the 10 and the 5 should cross together so the 5's slowness is absorbed inside the 10's, and a fast walker must be pre-positioned on the far side to return the flashlight. | Step | Move | Time | |---|---|---| | 1 | 1 & 2 cross → | 2 | | 2 | 1 returns ← | 1 | | 3 | 5 & 10 cross → | 10 | | 4 | 2 returns ← | 2 | | 5 | 1 & 2 cross → | 2 | | | Total | 17 | The greedy strategy (1 ferries each person across: 2+1+5+1+10 = 19) loses because the 5 and 10 each pay their cost separately. Strategy 17 "wastes" an extra round-trip of the fast pair to buy the 5∥10 pairing, accepting a small certain cost to cancel a big one. That trade is the whole puzzle. General rule for times a le b le c le d, price the two candidate strategies: - Pair the slow (the table above): b + a + d + b + b = a + 3b + d. Here 1 + 6 + 10 = 17. - Fast ferry (a escorts c and d separately): d + a + c + a + b = 2a + b + c + d. Here 19. Pairing wins exactly when 2b < a + c. For times 1, 2, 3, 4 the two strategies tie at 11, always evaluate both.

The Bridge at Night

Problem

Your answer

Hints

More Brainteasers & Logic to train on