The bridge at night
Four people must cross a narrow bridge at night with one torch. At most two can cross at once, and anyone crossing needs the torch. They take 1, 2, 5 and 10 minutes to cross, and a pair moves at the slower person's pace.
What is the shortest total time to get everyone across?
Show hint
Letting the fastest person escort everyone takes 19 minutes. Can you get the two slowest people across together?
Show solution
17 minutes.
- 1 and 2 cross (2 minutes).
- 1 returns with the torch (1).
- 5 and 10 cross together (10).
- 2 returns with the torch (2).
- 1 and 2 cross (2).
2 + 1 + 10 + 2 + 2 = 17. The obvious greedy plan is not optimal here, which is why searching every possibility, or a smarter argument, is sometimes needed.
Want a problem like this every day? See today's problem and keep a streak going.