Difficulty: Medium · Puzzle 5 of 6 · Topic: Classic Brain Teasers
Four people need to cross a bridge at night with one torch. At most two cross at once; pair speed is slower person's time. Times are 1, 2, 7, 10 minutes. Minimize total time.
Compare two strategies for moving the two slowest across.
1) Optimal pattern uses the two fastest as shuttles.
2) Send 1 and 2 across: +2.
3) Send 1 back: +1 (total 3).
4) Send 7 and 10 across together: +10 (total 13).
5) Send 2 back: +2 (total 15).
6) Send 1 and 2 across: +2 (total 17).
7) Alternate strategy (the fastest person escorts each slow person: 1+10 across, 1 back, 1+7 across, 1 back, 1+2 across) costs 10+1+7+1+2 = 21, so 17 is better. A Dijkstra search over all (torch side, who is where) states confirms 17 is the minimum.Answer: Minimum total crossing time is 17 minutes.
Checked by running a model of the rule in a Python model. A computational check: Dijkstra over every (who is on which side, torch side) state gives 17 for 1, 2, 7, 10 (escort strategy 21) and 17 for 1, 2, 5, 10 (escort strategy 19).
Greedy 'always send the fastest person with each slow person' costs 21 here, not 17; sending the two slowest together pays for the 10-minute walk only once.
For times 1, 2, 5, 10, what is the optimal total and why? Model answer: 17 again. Pair strategy costs 2+1+10+2+2 = 17, the escort strategy costs 10+1+5+1+2 = 19. The pair strategy wins when 2*t2 < t1 + t(n-1), i.e. 2*2 < 1+5 here; with 1, 2, 7, 10 it wins by an even larger margin (17 vs 21).
The idea is to pay for the two slowest people only once, by sending them together. So the one-minute and two-minute people cross first, which costs 2, then the one-minute person returns, costing 1, for a total of 3. Then the seven and the ten cross together for 10, total 13, the two-minute person comes back for 2, total 15, and finally the one and two cross for 2. The answer is 17 minutes. The trap is the greedy plan where the fastest escorts everyone, which costs 21.