Bridge and Torch (1, 2, 5, 10): Puzzle and Step-by-Step Solution
Logic & Strategy
Medium
Reported at Citadel, Optiver, SIG, Jane Street
The puzzle
Four people must cross a narrow bridge at night with a single torch. The bridge holds two at a time, and anyone crossing must carry the torch. They take 1, 2, 5 and 10 minutes to cross; a pair moves at the slower walker's pace. Can everyone cross in 17 minutes?
Short answer: Yes, in exactly 17: 1 and 2 cross, 1 returns, 5 and 10 cross, 2 returns, 1 and 2 cross.
Step 1: The obvious plan and why it fails
The instinct is to use the fastest walker as a ferry. The 1-minute walker escorts each of the others in turn and carries the torch back. That costs 10 + 1 + 5 + 1 + 2 = 19 minutes.
Look at where the 19 comes from: the 10 and the 5 are both paid in full on separate trips. Any plan that sends the two slow walkers separately pays at least 15 minutes for them before any return trips. To get under 19 you must stop paying for the 5.
Step 2: Send the slow pair together
If the 5 and the 10 cross together, that trip costs 10 and the 5 is absorbed inside it. But someone fast must already be on the far side to bring the torch back afterwards. So the schedule is: 1 and 2 cross (2 minutes). 1 returns (1). 5 and 10 cross (10). 2 returns (2). 1 and 2 cross (2).
Total: 2 + 1 + 10 + 2 + 2 = 17 minutes. The price of the clever plan is an extra return by the 2-minute walker, but that is cheaper than the 5 it saves.
Step 3: Proving 17 is optimal
Five crossings are needed: three forward trips of two people and two returns. The 10 must cross forward at least once, costing 10. The two returns cost at least 1 each, and if both are made by the 1-minute walker then the 5 and the 10 must cross on separate forward trips, which is the 19-minute plan. So in any faster plan one return is made by someone slower than 1, costing at least 2. The remaining two forward trips each cost at least 2. That gives 10 + 1 + 2 + 2 + 2 = 17 as a lower bound, and the schedule above meets it.
Step 4: The general rule
For speeds a ≤ b ≤ c ≤ d, compare two ways of moving the two slowest: the ferry costs c + d + 2a, and the paired move costs d + a + 2b. Pair the slow walkers whenever 2b < a + c. Here 2 × 2 = 4 is less than 1 + 5 = 6, so pairing wins by 2 minutes. With speeds 1, 4, 5 and 10, ferrying would win instead, which is a good follow-up to have ready.
Why interviewers ask it
Compute the greedy 19 first, notice it is too slow, and go hunting for overlapping cost. Interviewers are watching for the moment you question the greedy assumption.
Knowing the proof is half of it. Work Bridge and Torch (1, 2, 5, 10) interactively, then take it under a clock with the rest of the Outcry simulators.