A Rickety Bridge and One Decisive Vote

The Riddler for November 4, 2016. The Express is the classic bridge-and-torch crossing; the Classic asks how likely your single vote is to decide an election.

Riddler Express

Four people must cross a rickety bridge at night. It holds at most two at a time, and every crossing needs the group’s one flashlight, so someone must carry it back. The four walk at different speeds, taking $1$, $2$, $5$, and $10$ minutes; a pair crosses at the slower one’s pace. How quickly can all four get across?

The Riddler, FiveThirtyEight, November 4, 2016(original post)

Solution

The tempting plan is to let the fastest person, the one-minute walker, escort each of the others and run the flashlight back every time. That gives $10 + 1 + 5 + 1 + 2 = 19$ minutes, and it is not optimal. The waste is that the ten-minute crossing is paired with the one-minute walker, so the slowest trip carries almost no one else’s time with it.

The fix is to make the two slowest cross together, so the five-minute walker hides inside the ten-minute crossing and costs nothing extra. To set that up, send the two fastest over first and bring the quicker one back, then send the two slowest together, then have the already-waiting fast walker bring the flashlight back and finally cross with the other fast walker: $$\begin{aligned} &1\&2 \text{ cross } (2),\quad 1 \text{ back } (1),\quad 5\&10 \text{ cross } (10),\\ &2 \text{ back } (2),\quad 1\&2 \text{ cross } (2). \end{aligned}$$ The total is $2 + 1 + 10 + 2 + 2 = \boxed{17 \text{ minutes}}$. The single idea is to pair the two slow walkers so the board pays for ten and five at once rather than twice.

The computation

Encode the crossing as a shortest-path problem. A state is the set of people still on the start side together with which side holds the flashlight; a move sends one or two across in the flashlight’s direction at the slower walker’s cost. Dijkstra from “everyone on the start side” to “everyone across” gives the minimum time.

import heapq, itertools
times = (1, 2, 5, 10); everyone = frozenset(times)
start = (everyone, 'L')                      # people on left side, flashlight side
def moves(state):
    side, fl = state
    movers = side if fl == 'L' else (everyone - side)   # who can carry the light
    for grp in itertools.chain(itertools.combinations(movers, 1),
                               itertools.combinations(movers, 2)):
        cost = max(grp)
        nside = side - set(grp) if fl == 'L' else side | set(grp)
        yield (frozenset(nside), 'R' if fl == 'L' else 'L'), cost

dist = {start: 0}; pq = [(0, start)]
while pq:
    d, s = heapq.heappop(pq)
    if s == (frozenset(), 'R'): print("minimum time:", d); break
    if d > dist.get(s, 1e9): continue
    for ns, c in moves(s):
        if d + c < dist.get(ns, 1e9):
            dist[ns] = d + c; heapq.heappush(pq, (d + c, ns))
# minimum time: 17

Riddler Classic

You are the only sane voter in a state with two candidates. The other $N$ voters each flip a fair coin, independently, voting for either candidate with probability $\tfrac12$. What is the chance your vote changes the outcome toward your preferred candidate, and how does that chance scale with $N$?

The Riddler, FiveThirtyEight, November 4, 2016(original post)

Solution

Your vote matters only when it breaks a tie. Adding your ballot for your candidate flips the result from a loss or tie to a win exactly when the other $N$ voters split evenly, $\tfrac N2$ each (take $N$ even; an odd $N$ only ever lets you force a tie, and the size estimate is unchanged for large $N$). The number voting for one candidate is a sum of $N$ fair coins, a binomial count, so the chance of a dead-even split is $$P = \binom{N}{N/2}\left(\tfrac12\right)^{N/2}\left(\tfrac12\right)^{N/2} = \boxed{\dfrac{1}{2^N}\binom{N}{N/2}}.$$ To see how this behaves as the electorate grows, apply Stirling’s approximation $n! \approx \sqrt{2\pi n}\,(n/e)^n$ to the central binomial coefficient, which gives $\binom{N}{N/2} \approx 2^N \big/ \sqrt{\pi N/2}$, and the powers of two cancel: $$P \approx \sqrt{\dfrac{2}{\pi N}} .$$ So your influence fades like $1/\sqrt N$, not like $1/N$. Doubling the state’s population multiplies your chance of being decisive by $1/\sqrt2 \approx 0.707$, a far gentler decline than intuition suggests: in a state of a million other voters you still swing the result about once in $1{,}250$ elections.

The computation

Encode both halves. Confirm the exact formula against a direct simulation of $N$ coin-flip voters, and check the Stirling approximation and the $1/\sqrt N$ scaling across a range of $N$.

from math import comb, sqrt, pi
import random
def exact(N):  return comb(N, N // 2) / 2**N
def approx(N): return sqrt(2 / (pi * N))

def simulate(N, trials=2_000_000, seed=0):
    rng = random.Random(seed); ties = 0
    for _ in range(trials):
        if sum(rng.getrandbits(1) for _ in range(N)) == N // 2: ties += 1
    return ties / trials

for N in (10, 100, 1000):
    print(f"N={N:5d}: exact={exact(N):.5f}  approx={approx(N):.5f}  sim={simulate(N, 400000):.5f}")
print("doubling N -> factor", round(exact(2000) / exact(1000), 4), "(1/sqrt2 =", round(1/sqrt(2), 4), ")")
# N=   10: exact=0.24609  approx=0.25231  sim=0.24561
# N=  100: exact=0.07959  approx=0.07979  sim=0.07897
# N= 1000: exact=0.02523  approx=0.02523  sim=0.02543
# doubling N -> factor 0.7072 (1/sqrt2 = 0.7071 )