Can You Navigate The One-Way Streets?

Riddler Express

Two cups start with equal water. Repeatedly pour half of cup A into B, then half of B back into A, many times. What fraction of the water ends up in A? Extra credit: what if the cups start with arbitrary (non-zero) amounts?

Solution

Normalise the total to $1$ and let $a$ be the fraction in A. One full round does two pours. First half of A goes to B: A holds $\tfrac{a}{2}$, B holds $b + \tfrac{a}{2}$. Then half of B returns: B keeps $\tfrac12\big(b + \tfrac{a}{2}\big)$ and A gains the rest, so $$a \;\longmapsto\; \frac{a}{2} + \frac12\Big(b + \frac{a}{2}\Big) = \frac{3a}{4} + \frac{b}{2}.$$ At a steady state this equals $a$; with $b = 1 - a$, $$\frac{3a}{4} + \frac{1 - a}{2} = a \;\Longrightarrow\; \frac{1 - a}{2} = \frac{a}{4} \;\Longrightarrow\; a = \boxed{\tfrac23}.$$ The map contracts toward this fixed point regardless of the starting split, so the cups always settle at $\tfrac23$ in A and $\tfrac13$ in B, whatever the (non-zero) initial amounts.

The computation

Iterate the two pours many times from different starting amounts and read off the fraction in A.

def fraction_A(a, b, rounds=100):
    for _ in range(rounds):
        a /= 2; b += a; b /= 2; a += b
    return a / (a + b)
print(fraction_A(8, 8), fraction_A(3, 5))      # 0.6667, 0.6667

Riddler Classic

A $2\times 2$ block of city streets is a $3\times 3$ grid of corners joined by $12$ blocks; each block is given a random one-way direction. You commute from the top-left corner to the bottom-right. What is the probability a route still exists? And the probability of a round trip?

Solution

Number the corners $1$ through $9$ across the grid; the $12$ blocks each get one of two directions, so there are $2^{12} = 4096$ equally likely street layouts. The question is purely combinatorial: in how many of them is corner $9$ reachable from corner $1$. Checking every layout for a directed path, exactly $1135$ work, so $$\Pr(\text{commute possible}) = \frac{1135}{4096} \approx \boxed{0.277}.$$ Requiring a path back as well (a round trip, $1 \to 9$ and $9 \to 1$) is far more demanding; only $170$ layouts manage it, $$\Pr(\text{round trip}) = \frac{170}{4096} = \frac{85}{2048} \approx \boxed{0.0415}.$$

The computation

Enumerate all $2^{12}$ orientations of the twelve blocks, build the directed graph for each, and count those with a path from start to work (and back).

from itertools import product
import networkx as nx
edges = [(1,2),(2,3),(1,4),(2,5),(3,6),(4,5),
         (5,6),(4,7),(7,8),(5,8),(6,9),(8,9)]
go = back = 0
for dirs in product((0, 1), repeat=12):
    g = nx.DiGraph()
    for (u, v), d in zip(edges, dirs):
        g.add_edge(u, v) if d == 0 else g.add_edge(v, u)
    if nx.has_path(g, 1, 9):
        go += 1
        if nx.has_path(g, 9, 1): back += 1
print(go, back)                                # 1135, 170  (of 4096)