Bridge and Lantern Crossing Optimization
Four traders need to cross a narrow bridge at night. They have a single lantern, and at most two people can cross at a time. When two people cross together, they move at the speed of the slower person. Someone must carry the lantern back after each crossing so the next pair can go.
The four traders have crossing times of
$,
$, $7$, and 0$ minutes. The person returning the lantern does not need to be from the most recent pair -- anyone on the starting side can bring it back.
1. Find the minimum total time needed to get all four traders across the bridge.
2. There are two natural strategies: the **shuttle strategy** (the fastest person escorts everyone across one by one) and the **pairing strategy** (send the two slowest together so they only cost one slow crossing). Compare these strategies and prove which one is optimal for the given times.
3. Generalize to $n$ people with sorted crossing times $t_1 \le t_2 \le \cdots \le t_n$. Give a general procedure for optimal crossing and prove it.
Open the full interactive solver, hints, and worked solution →