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 $1$, $2$, $7$, and $10$ 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.
- Find the minimum total time needed to get all four traders across the bridge.
- 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.
- 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.
Hints
- There are really only two ideas: either the fastest person escorts everyone, or you find a way to make the slow people cross together so you pay for the slowest only once.
- Compare the cost of the shuttle strategy ($t_2 + t_3 + t_4 + 2t_1$) to the pairing strategy ($t_4 + 2t_2 + t_1$). The difference depends on $t_1 + t_3 - 2t_2$.
- To prove optimality, argue that any valid schedule with $n = 4$ needs exactly 3 forward crossings and 2 returns, and the two strategies above are the only non-dominated options for how to assign people to those crossings.
Worked Solution
How to Think About It: The core tension is the return trip. Every crossing of two people requires someone to bring the lantern back, and that return trip is pure overhead. The question is: how do you minimize the cost of these return trips while also avoiding the disaster of having slow people cross separately (which makes you pay their cost multiple times)? There are really only two ideas worth considering. Either the fastest person shuttles everyone across, or you pair the slow people together so their cost is paid only once.
Quick Estimate: With times $1, 2, 7, 10$, the shuttle strategy (person 1 escorts everyone) costs $2 + 1 + 7 + 1 + 10 = 21$ minutes -- you pay 1 minute for each return trip, but you pay the full 7 and 10 separately. The pairing strategy sends 1 and 2 across first ($2$ min), 1 returns ($1$ min), then 7 and 10 cross together ($10$ min), 2 returns ($2$ min), then 1 and 2 cross again ($2$ min). Total: $2 + 1 + 10 + 2 + 2 = 17$ minutes. Pairing saves 4 minutes because the 7-minute person's crossing is hidden inside the 10-minute crossing.
Approach: We compare the two strategies algebraically, then prove no other strategy can do better.
Formal Solution:
Label the crossing times $t_1 \le t_2 \le t_3 \le t_4$ with values $1, 2, 7, 10$.
Strategy 1 -- Shuttle (fastest escorts all): - $t_1$ and $t_3$ cross: $t_3$ minutes. $t_1$ returns: $t_1$ minutes. - $t_1$ and $t_4$ cross: $t_4$ minutes. $t_1$ returns: $t_1$ minutes. - $t_1$ and $t_2$ cross: $t_2$ minutes. - Total: $t_2 + t_3 + t_4 + 2t_1 = 2 + 7 + 10 + 2 = 21$ minutes.
Strategy 2 -- Pairing (slowest pair together): - $t_1$ and $t_2$ cross: $t_2$ minutes. $t_1$ returns: $t_1$ minutes. - $t_3$ and $t_4$ cross: $t_4$ minutes. $t_2$ returns: $t_2$ minutes. - $t_1$ and $t_2$ cross: $t_2$ minutes. - Total: $t_4 + 2t_2 + t_1 = 10 + 4 + 1 + 2 = 17$ minutes.
The difference is:
$$\text{Shuttle} - \text{Pairing} = (t_3 + 2t_1) - (2t_2) + (t_2 - t_2) = t_3 - 2t_2 + 2t_1$$
More precisely:
$$\Delta = (t_2 + t_3 + t_4 + 2t_1) - (t_4 + 2t_2 + t_1) = t_3 - t_2 + t_1 - t_2 + t_2 = t_3 + t_1 - 2t_2$$
Simplifying: $\Delta = t_1 + t_3 - 2t_2$. For our values: $1 + 7 - 4 = 4 > 0$, so Shuttle costs 4 more minutes. Pairing wins.
Pairing is better when $t_1 + t_3 > 2t_2$, i.e., when $t_3 - t_2 > t_2 - t_1$. In words: pairing wins when the gap between the third and second person is larger than the gap between the second and first -- because you are paying $t_2$ for return trips instead of $t_1$, but you save the full difference $t_3 - t_2$ by hiding person 3 inside person 4's crossing.
Proof of optimality for $n = 4$:
Any valid schedule consists of 5 crossings: 3 forward (moving people to the far side) and 2 returns. Every forward crossing moves at most 2 people, and we need to move 4 people total. So we need at least 3 forward trips with 2 returns.
Key observations: - Each return trip costs at least $t_1$ (the fastest available person returns). - The two slowest people ($t_3, t_4$) must each cross at least once. If they cross separately (in different forward trips), we pay at least $t_3 + t_4$. If they cross together, we pay only $t_4$. - When they cross together, the lantern must already be on the starting side and someone fast must have brought it back. The cheapest way to set this up is to send $t_1, t_2$ across first (cost $t_2$), return $t_1$ (cost $t_1$), then send $t_3, t_4$ (cost $t_4$), return $t_2$ (cost $t_2$), then send $t_1, t_2$ again (cost $t_2$).
Any other schedule either sends $t_3$ and $t_4$ separately (paying $t_3 + t_4$ in forward crossings) or pairs them but uses a suboptimal return arrangement. The two strategies above are the only candidates, and we pick whichever gives the smaller total.
Generalization to $n$ people:
For $n$ people with sorted times $t_1 \le t_2 \le \cdots \le t_n$, process people from the slowest pair down. At each step, we have the two slowest remaining people to move. We choose between:
- Shuttle: Fastest person escorts them one at a time. Cost for moving persons $i$ and $i-1$: $t_i + t_{i-1} + 2t_1$ (two forward trips plus two returns).
- Pairing: Send $t_1, t_2$ across, $t_1$ returns, send $t_{i-1}, t_i$ across, $t_2$ returns. Cost: $t_i + 2t_2 + t_1$.
Pairing is better when $t_{i-1} + 2t_1 > 2t_2 + t_1$, i.e., $t_{i-1} - t_2 > t_2 - t_1$. We apply this decision greedily for each pair $(t_{n}, t_{n-1})$, $(t_{n-2}, t_{n-3})$, etc., working from the slowest to the fastest. If $n$ is odd, the last remaining person crosses with $t_1$ using the shuttle method (cost $t_{\text{remaining}} + t_1$).
The total minimum time is:
$$T^{*} = \sum_{\text{pairs}} \min\left(t_i + t_{i-1} + 2t_1,\; t_i + 2t_2 + t_1\right)$$
where the sum is taken over pairs $(t_n, t_{n-1}), (t_{n-2}, t_{n-3}), \ldots$, plus $t_1$ added once at the end for the final crossing of person 1 (if not already counted).
Answer: The minimum total time for crossing times $1, 2, 7, 10$ is $\boxed{17}$ minutes, achieved by the pairing strategy: send 1 and 2 across (2 min), 1 returns (1 min), 7 and 10 cross together (10 min), 2 returns (2 min), 1 and 2 cross (2 min). In general, optimality requires choosing between shuttle and pairing for each pair of slow people: pair them when $t_{i-1} + t_1 > 2t_2$, shuttle them otherwise.
Intuition
The deep insight here is about hidden costs. When two people cross together, the slower person's time is "free" -- it is absorbed into the crossing that was going to happen anyway. The entire puzzle reduces to: which slow crossings can you hide inside other slow crossings, and what is the cheapest way to shuttle the lantern back to enable that pairing? The shuttle strategy minimizes return trip costs (always send the fastest back) but pays full price for every slow person individually. The pairing strategy pays more for returns (the second-fastest person returns instead of the fastest) but saves a huge amount by bundling the two slowest together.
This trade-off -- cheap overhead vs. expensive individual costs -- shows up constantly in operations research and scheduling. In trading, the analogue is transaction cost optimization: sometimes it is cheaper to batch two large orders together (paying a slightly higher market impact once) than to execute them separately (paying moderate impact twice). The general solution's greedy pair-by-pair comparison is a clean example of how local optimality gives global optimality when the subproblems are independent.