Section 29.2

Crossings and Transport

Bridge and river crossings, camel-and-bananas depots, couriers.

Toolkit

These problems concern minimising crossings, trips, or resource loss under capacity constraints (boat size, lantern count, carrying capacity). The common technique: identify the bottleneck constraint, and design a repeating cycle or greedy sequence that pays the “fixed cost” (a return trip, a slow walker, a consumed resource) as few times as possible.

Key facts:

Boat/ferry puzzles: with capacity 2 and $n$ conflicting items, look for an invariant (parity, who must return) forcing a minimum number of crossings; verify via a repeatable cycle of moves.
Bridge crossing with lantern: total time for $n$ people crossing two at a time, carrying one lantern that must return, is minimised by pairing the two slowest together once, so their times are counted only once, while fast people shuttle the lantern back:
$T=\text{(fast shuttling costs)}+\max(\text{two slowest}).$
Jeep/camel-bananas: if one load of supplies covers distance $d$ and $k$ loads are present, moving all $k$ loads forward a distance $x$ costs $kx$ units of fuel/bananas (since each unit distance needs $k$ traversals net). Optimal strategy advances with $k$ loads until exactly one load’s worth is consumed, then switches to $k-1$ loads, giving total distance
$D=\sum_{i=1}^{k}\frac{d}{2i-1}$
for the classic one-way version with full return trips.

Problems