It is night. Four people must cross a narrow, shaky bridge. There is one torch, and nobody can step on the bridge without it. The bridge holds at most two. One person crosses in 1 minute, another in 2, the third in 5 and the fourth in 10. A pair walks together with the torch at the slower one's pace. The torch cannot be thrown across: someone has to carry it back. What is the fewest minutes for all four to reach the other side?
It looks as if the fastest should walk everyone over and bring the torch back each time: 10 + 1 + 5 + 1 + 2 = 19. But if the two slowest cross together, the 5 minutes of one hide inside the 10 minutes of the other. The price: an extra crossing by the pair 1 and 2 (2 minutes) and the 2 bringing the torch back instead of the 1 (1 more minute). 19 − 5 + 2 + 1 = 17.
This puzzle is asked at job interviews to see how a candidate looks for the best plan rather than the first one that comes to mind. Behind it are shortest paths in a graph of states and a recurrence that Günter Rote proved in 2002.
Narrow and shaky, it holds at most two people at a time. There is no other way to the far side.
There is one torch. Nobody can walk the bridge without it, so every crossing, there or back, is made by someone holding the torch. It cannot be thrown across.
The four cross in 1, 2, 5 and 10 minutes. Two people walk together at the slower one's pace: the pair 2 and 10 takes 10 minutes.
What is the fewest number of minutes in which all four can be on the far side?
"The fastest escorts everyone: 10 + 1 + 5 + 1 + 2 = 19 minutes"
The logic is clear: the fastest walker brings the torch back every time, so each return costs only a minute. But then 5 and 10 cross separately and occupy the bridge for 15 minutes between them. Send them together and you get 17.
1, 2, 5 and 10 minutes, a bridge for two, one torch. Lock in the least time you think is possible.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
"The fastest escorts everyone" is not the only plan. Look at how many minutes 5 and 10 cost when they cross separately.
Send 5 and 10 together so the 5 minutes hide inside the 10. But then someone fast must already be waiting on the far side to bring the torch back.
Start like this: 1 and 2 cross, 1 comes back. Who should go over next, who brings the torch back, and who is left? Add up the minutes.
Click one or two people on the torch side and press "Cross". The clock counts the minutes. Then pick a rule in the right-hand card: the page goes through every set of times and looks for one where the rule loses to the best schedule.
Each person crosses in a random whole number of minutes from 1 to 20, all equally likely. For each set the page finds the best schedule by a full search over states (Dijkstra's algorithm) and compares it with two simple rules. Bars show the exact shares, counted over every possible set; dots show the shares in the simulation.
A rule counts as best if it reaches the optimal time. When both rules tie at the optimum, the set counts for both, so the shares can add up to more than 100%.
The whole difference is in who walks with the slow ones and who carries the torch back. Here are five ways to see it.
A pair walks at the slower one's pace, so whoever walks with the 10-minute person rides for free, and it pays most when that companion is slow too. Putting the 1-minute walker next to the 10 wastes their speed. The most expensive thing in the puzzle is the slow walkers' minutes, and it pays to hide one inside the other.
At most two go over at a time, and one person brings the torch back. Each there-and-back pair of trips moves only one person net, so four people need at least three trips over and two back. Returns are unavoidable; the only question is who makes them. The 17-minute schedule pays one minute more on returns, but the way over costs 2 + 10 + 2 = 14 minutes instead of 10 + 5 + 2 = 17. In total 14 + 3 = 17 against 17 + 2 = 19.
For four people the difference between the two plans is t₁ + t₃ − 2t₂. Sending the two slow ones together pays when the two "shuttles", the fastest and the second fastest, are quicker between them than the fastest and the third.
A schedule of five crossings: a pair over (6 choices), one back (2), a pair over (3), one back (3), a pair over (1). In total 6 · 2 · 3 · 3 · 1 = 108. The page has just gone through all of them: the least time is 17 minutes, and only two schedules give it, differing in who comes back first, 1 or 2. Longer schedules, with seven or more crossings, are covered by the full search in round 3: none beats 17.
d(v) = minu → v ( d(u) + w(u, v) )
A state of the crossing says who is on which bank and where the torch is: 2⁴ · 2 = 32 possibilities, of which 30 are reachable. A crossing with cost w links two states, and the puzzle becomes a shortest-path search in a graph. Dijkstra's algorithm settles states in order of increasing distance d and guarantees the optimum. The rule "the fastest escorts everyone" is greedy: it makes every return as cheap as possible but ignores what the way over will cost. The shortest path sometimes starts with a dearer step.
Sort the times. The two slowest are moved in one of two ways, and the problem shrinks by two people.
The first term in the min: the two fastest act as shuttles and the two slowest go together. The second: the fastest escorts each of the two.
For 1, 2, 5, 10: first move 5 and 10, then 1 and 2 remain.
In 2002 Günter Rote proved that this recurrence always gives the optimum, for any number of people. The choice is made afresh at each step: with six people it can pay to send the two slowest together and then escort the next two one by one. The page checked the recurrence against a full search in round 3.
The bridge puzzle teaches a simple thing: it pays to group the expensive items together. In mathematics this is a recurrence for any number of people. In logic it is the gap between a locally sensible step and the best plan. In practice the same trick cuts computing time.
Mathematics
For a bridge for two, Rote's recurrence works for any number of people: sort the times and keep moving the two slowest in the cheaper way. The table on the left shows every step. The count takes only a handful of operations even for a thousand people.
If the bridge holds three, no simple formula is in sight, and the page searches for the shortest path in the graph of states. For 1, 2, 5, 10 the answer is 13 minutes: 1, 5 and 10 go together (10), 1 comes back (1), 1 and 2 cross (2). Same idea: the slow walkers hide their minutes in one crossing.
Logic
First move the two 20-minute walkers, then 4 and 5, finally 1 and 3. Pick the method for each pair.
Each of the two rules makes sense at its own step. "The fastest escorts" minimises the returns. "The two slowest together" minimises the way over. But the best plan here is mixed: the two 20-minute walkers should go together, while 4 and 5 are better escorted one by one. For six people with times from 1 to 20 this happens in about 29% of sets (round 3).
The general lesson: optimise the bottleneck. The most expensive minutes in this puzzle belong to the slowest walkers, and the plan should be built around them, not around whoever runs back and forth most conveniently. The same lesson appears in the poisoned wine puzzle: what matters is not each step but the whole scheme.
Practice
Eight jobs of 1, 2, 3, 4, 10, 11, 12, 13 minutes. A machine runs them in batches, and a batch lasts as long as its longest job. Batches run one after another.
If a batch lasts as long as its longest job, putting a short job next to a long one wastes a slot: the short one waits anyway. Sort the jobs and cut them into consecutive batches from the longest: with batches of 2 this gives 13 + 11 + 4 + 2 = 30 minutes instead of 46 when every fast job is paired with a slow one. A search over all splits confirms that 30 is the best.
This is done when training neural networks: sentences of different lengths are padded to the longest in a batch, so they are grouped by length to keep short ones from waiting for long ones. The same goes for CI: long tests go into one run rather than being spread across all of them. The bridge has one more twist that batches lack: the torch must come back, which is why the two fast walkers become shuttles.
The puzzle appears at least as early as 1981, in the book "Super Strategies for Puzzles and Games" by Saul Levmore and Elizabeth Cook. There four men in enemy territory cross a bridge over a ravine with a lantern: 5, 10, 20 and 25 minutes, one hour for all.
The best-known interview version: the four members of U2 (1, 2, 5 and 10 minutes) must cross before the bridge collapses in 17 minutes. William Poundstone described it in 2003 in "How Would You Move Mount Fuji?", a book about puzzle interviews at Microsoft. The story that Microsoft gave it to every applicant goes back to a 1998 chain e-mail.
Günter Rote of the Free University of Berlin published "Crossing the bridge at night" in the Bulletin of the EATCS (volume 78, October 2002) and proved that the recurrence with two ways of moving the slowest pair is always optimal. Torsten Sillke had conjectured it, and a few months earlier the same bulletin had printed a paper by Cristian and Elena Calude with a wrong general answer.
Four people have exactly 108 schedules without wasted crossings. Only 2 of them take 17 minutes, 6 take 19, and the worst takes 50 minutes.
Edsger Dijkstra published his shortest-path algorithm in 1959 in "A note on two problems in connexion with graphs" in Numerische Mathematik. It is what searches the states of the crossing in round 3.
In 2008 Roland Backhouse analysed the general case where the bridge holds C people, in "The capacity-C torch problem" at the Mathematics of Program Construction conference (Marseille).
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.