Four people must cross a bridge at night with one torch. The bridge carries two at a time, a pair moves at the slower person's pace, and the torch must be carried back for the next group. Their crossing times are 1, 2, 5 and 10 minutes. What is the minimum total time?

Four people must cross a bridge at night with one torch. The bridge carries two at a time, a pair moves at the slower person's pace, and the torch must be carried back for the next group. Their crossing times are 1, 2, 5 and 10 minutes. What is the minimum total time?

Approach: Compare the escort plan where the fastest person walks everyone over with the plan that sends the two slowest together, and count the return trips each needs.

17 minutes. Send 1 and 2 over for 2, return 1 for 1, send 5 and 10 together for 10, return 2 for 2, then send 1 and 2 for 2, giving 2 + 1 + 10 + 2 + 2 = 17. The idea is pairing the slowest two so that 10 covers 5 for free, while the two fastest act as the shuttle. The greedy escort plan where 1 walks everybody across costs 10 + 1 + 5 + 1 + 2 = 19, which is worse because 5 then pays for its own crossing separately. The lower bound is 17: three forward trips are needed, 10 must appear in one of them, 5 must either share that trip or add 5 of its own, and two returns cost at least 1 + 2.

Follow-up: With times 1, 2, 5, 10 and 20 for five people, what is the minimum total crossing time?

Key concepts: pairing the slowest, shuttle strategy, greedy failure.