Four people, one torch, a 17-minute bridge.
The bridge-and-torch puzzle: four people with crossing times of 1, 2, 5, and 10 minutes share one torch, and the bridge holds two at a time. Everyone assumes the fastest walker should escort each crossing. That obvious strategy is wrong, and the reason it is wrong is the whole lesson.
Four people arrive at night on the near side of a rickety bridge. The bridge holds at most two people at once, and anyone crossing must carry the group's single torch; it is too dark and too dangerous otherwise. The torch cannot be thrown across, so someone has to walk it back.
The four walk at very different speeds. Alone or in a pair, a crossing takes as long as the slower walker: 1 minute for the fastest person, 2 for the next, 5 for the third, and 10 for the slowest.
Get all four across in 17 minutes.
The obvious plan is to use the 1-minute walker as a ferry: escort the 10, come back, escort the 5, come back, cross with the 2. That costs 10 + 1 + 5 + 1 + 2 = 19 minutes. When this puzzle circulated as a Microsoft interview question in the late 1990s, plenty of candidates stopped at 19 and defended it, because "the fastest person shuttles the torch" feels self-evidently optimal. The interviewer would then say only: 17 is possible.
That gap between 19 and 17 is the entire puzzle. Before opening hints, interrogate the greedy plan: where exactly does it waste time? Look at what the two slowest people cost you under the ferry scheme, separately, and ask whether those two costs must both be paid in full.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
In the 19-minute ferry plan, the 10-minute crossing and the 5-minute crossing are paid separately: 15 minutes of the total go to the two slow walkers alone. Is there a way to pay for both slow people during the same crossing?
Hint 2 the key move
Send the 5 and the 10 across together. That crossing costs 10, and the 5 walks free in its shadow. But pairing the slow two creates a new problem: someone has to bring the torch back, and it must not be the 5 or the 10. Who is waiting on the far side, and how did they get there?
Hint 3 nearly the answer
Pre-position the fast pair: send 1 and 2 over first, and have one of them wait on the far side while the other runs the torch back. Then the slow pair crosses, and the waiting fast walker returns the torch for the final trip. Add it up.
The solution
Reveal the full solution
Five crossings, 17 minutes:
- 1 and 2 cross together: 2 minutes.
- 1 returns with the torch: 1 minute. (Total 3.)
- 5 and 10 cross together: 10 minutes. (Total 13.)
- 2 returns with the torch: 2 minutes. (Total 15.)
- 1 and 2 cross again: 2 minutes. (Total 17.)
The ferry plan loses because it pays the 10 and the 5 as separate line items. Pairing the slow walkers merges those costs: the 5's crossing time vanishes inside the 10's. The price of the merge is overhead, two extra trips by the fast pair to pre-position a torch-returner on the far side. Here the overhead is 2 + 2 = 4 minutes of fast-pair crossings plus 1 for the return, against 5 minutes saved by hiding the second-slowest crossing, so the trade wins by 2.
That trade is not always right, which is what makes the puzzle honest. Compare the two strategies for moving the slowest pair in general: the ferry costs t1 + t4 plus t1 + t3 across its two slow deliveries, while the pairing scheme costs t2 + t1 + t4 + t2 for the same progress. Cancel the shared terms and the pairing wins exactly when 2 t2 < t1 + t3. With times 1, 2, 5, 10: 4 < 6, so pair. With times 1, 4, 5, 10: 8 > 6, and the despised ferry plan is optimal after all. An interviewer who follows up with new numbers is checking whether you found the condition or memorised the trick.
What this puzzle is really testing
Whether you treat a plausible greedy rule as a conclusion or as a hypothesis. "Fastest walker escorts everyone" optimises each crossing locally and loses globally, the signature failure mode of greedy reasoning, and the fix is an exchange argument of exactly the kind that justifies real greedy algorithms when they are correct. The Dijkstra invariant deep-dive shows what a greedy proof obligation looks like when it succeeds. And if you want the sledgehammer: the puzzle is a shortest-path search over states (who is on which side, where the torch is), solvable mechanically with the tools in the graphs module. Sixteen states, weighted edges, done. Knowing both the insight and the sledgehammer is the difference between solving this puzzle and understanding it.
Follow-ups to expect
Five people with times 1, 2, 5, 10, 25 (answer: 30, and the 2 t2 condition gets applied once per slow pair). The general n-person algorithm, which sorts the times and repeatedly chooses between the two strategies above. And a quieter cousin of this cost structure appears in the two-egg drop puzzle, where the right strategy also balances unequal costs instead of splitting evenly.