Solution
The Feuding Hikers on the Bridge
Show the problem again
Five hikers must cross a narrow bridge at night. They need 1, 2, 5, 8 and 12 minutes respectively to cross alone. The bridge holds at most two people at once, they must carry the single torch with them each time (it cannot be thrown), and a pair crosses at the slower member's pace. The hikers who take 1 and 2 minutes have fallen out: at no time may those two be alone together. That means they may not cross the bridge as a pair, and the pair may not be the only two people standing on either bank. What is the minimum total time, in minutes, for all five to get across?
Worked solution
The answer is 37 minutes. Without the feud the best total is 25 (cross 1 and 2, return 1, cross 8 and 12, return 2, cross 1 and 2, return 1, cross 1 and 5). With the feud, the fast pair cannot shuttle together, which wrecks that plan. A Dijkstra search over all states (who is on which side, where the torch is) confirms 37, achieved by: 2 and 5 cross (5), 5 returns (5), 1 and 5 cross (5), 1 returns (1), 1 and 8 cross (8), 1 returns (1), 1 and 12 cross (12), for 5 + 5 + 5 + 1 + 8 + 1 + 12 = 37. The slow hikers must always be used as chaperones, because only a third person can separate the two fastest.
Source: Original variation on the classic bridge-and-torch puzzle, written for AxiomIQ.