Night Falls. A Storm Rolls In. Can You Cross The River?

You’re on the north shore of a river, and want to cross to the south, via a series of 13 bridges and six islands, which you can see in the diagram below. But, as you approach the water, night falls, a bad storm rolls in, and you’re forced to wait until morning to try to cross. Overnight, the storm could render some of the bridges unusable: it has a 50 percent chance of knocking out each of the bridges. (The chance is independent for each bridge.)

What’s the probability you will be able to cross the river in the morning? (You have no boat, can’t swim, can’t fix the bridges, etc. No tricks.)

The Riddler, FiveThirtyEight(original post)

Solution

The picture rewards a second look before any calculation. You cross in the morning exactly when the surviving bridges still join the north shore to the south. Picture the rival event from the storm’s side: the knocked-out bridges, threaded together, joining the west bank to the east bank in an unbroken wall across your path. Because the bridge network is drawn flat with no crossings, exactly one of these two things must hold. Either a chain of standing bridges runs north to south and you cross, or a chain of fallen bridges runs west to east and dams you in; a planar network admits a crossing path or a blocking cut, never both and never neither.

So $\Pr(\text{you cross}) + \Pr(\text{you are blocked}) = 1$. The two probabilities are in fact equal, and this is the elegance the diagram was built for. The arrangement of islands and bridges is self-dual: replace each bridge by a link joining the two land masses it separates, and the new “barrier network” is an identical copy of the original, with a standing bridge in one corresponding to a fallen bridge in the other. Since every bridge stands or falls by an independent fair coin, swapping standing for fallen leaves the probabilities untouched. Hence a north-south crossing and a west-east barrier are equally likely: $$\Pr(\text{you cross}) = \Pr(\text{you are blocked}) = \tfrac12.$$ The probability of getting across is therefore $\boxed{\tfrac12}$, independent of the exact size of this self-dual map.

The computation

The duality argument deserves a blunt check. There are only $2^{13}=8192$ ways the storm can leave the bridges standing or fallen, each equally likely, so enumerate them all: for each, keep the standing bridges and test by breadth-first search whether the north shore still reaches the south. The exact fraction that connect is the answer.

from itertools import product
from collections import defaultdict
# 0 = north shore, 7 = south shore, 1..6 = islands
bridges = [(0,1),(0,2),(0,3),(1,2),(1,4),(2,3),(2,5),
           (3,6),(4,5),(4,7),(5,6),(6,7),(7,5)]
def connects(standing):
    g = defaultdict(list)
    for k, (u, v) in enumerate(bridges):
        if standing[k]:
            g[u].append(v); g[v].append(u)
    seen, stack = {0}, [0]               # walk from the north shore
    while stack:
        x = stack.pop()
        for y in g[x]:
            if y not in seen:
                seen.add(y); stack.append(y)
    return 7 in seen                     # did we reach the south shore?
good = sum(connects(s) for s in product((0, 1), repeat=len(bridges)))
print(good, 2**len(bridges), good / 2**len(bridges))   # 4096 8192 0.5