Tetris Tilings and a Splitting Microbe

The Riddler for January 27, 2017. The Express counts the ways tetrominoes pave a thin strip; the Classic is a branching process with a sharp survival threshold.

Riddler Express

In Tetris you can sometimes clear the board after placing five pieces. How many arrangements of tetrominoes form a solid block two squares high and ten squares wide?

The Riddler, FiveThirtyEight, January 27, 2017(original post)

Solution

We are tiling a $2\times 10$ rectangle with tetrominoes (every orientation of the seven shapes is allowed), which is a finite count best done by careful bookkeeping. The clean way is to fill the strip column by column and, whenever the leftmost empty cell appears, try every piece that can cover it. Counting all completions gives $$\boxed{64}$$ arrangements. There is a pretty pattern across widths: the two-row strips of width $2, 4, 6, 8, 10$ give $1, 4, 9, 25, 64$. These are the squares of the Fibonacci numbers: the width-$2k$ strip has $F_{k+1}^2$ tilings, and $F_6^2 = 64$.

The computation

Encode the tiling search: list every orientation of the tetrominoes that fits two rows, fill the leftmost empty cell each step, and count complete tilings. Run it across widths to see the Fibonacci-squared pattern.

def orientations():                          # all tetromino orientations fitting 2 rows
    base = {'I':[(0,0),(0,1),(0,2),(0,3)], 'O':[(0,0),(0,1),(1,0),(1,1)],
            'T':[(0,0),(0,1),(0,2),(1,1)], 'S':[(0,1),(0,2),(1,0),(1,1)],
            'Z':[(0,0),(0,1),(1,1),(1,2)], 'L':[(0,0),(1,0),(1,1),(1,2)],
            'J':[(0,0),(0,1),(0,2),(1,2)]}
    rot = lambda c: [(y, -x) for x, y in c]
    norm = lambda c: frozenset((x - min(a for a,_ in c), y - min(b for _,b in c)) for x, y in c)
    sh = set()
    for cells in base.values():
        c = cells
        for _ in range(4):
            sh.add(norm(c)); sh.add(norm([(x, -y) for x, y in c])); c = rot(c)
    return [s for s in sh if max(x for x, _ in s) <= 1]

SH = orientations()
def tilings(W, R=2):
    idx = lambda r, c: r * W + c
    def solve(occ):
        pos = next(((r, c) for c in range(W) for r in range(R) if not (occ >> idx(r, c)) & 1), None)
        if pos is None: return 1
        r0, c0 = pos; total = 0
        for s in SH:
            ar, ac = sorted(s, key=lambda p: (p[1], p[0]))[0]; mask = 0; ok = True
            for dr, dc in s:
                rr, cc = r0 + dr - ar, c0 + dc - ac
                if not (0 <= rr < R and 0 <= cc < W) or (occ >> idx(rr, cc)) & 1: ok = False; break
                mask |= 1 << idx(rr, cc)
            if ok: total += solve(occ | mask)
        return total
    return solve(0)
print("2x10:", tilings(10))
print("widths 2,4,6,8,10:", [tilings(w) for w in (2, 4, 6, 8, 10)])
# 2x10: 64
# widths 2,4,6,8,10: [1, 4, 9, 25, 64]

Riddler Classic

At the start of time there is one microorganism. Each day, every member of the species either splits into two copies (with probability $p$) or dies. What is the probability the species eventually goes extinct?

The Riddler, FiveThirtyEight, January 27, 2017(original post)

Solution

Let $q$ be the extinction probability starting from one microbe. On day one it either dies (probability $1-p$, instant extinction) or splits into two, after which the line dies out only if both offspring lineages die out. The two lineages are independent copies of the original problem, so each dies out with probability $q$, and $$q = (1-p) + p\,q^2.$$ This quadratic has roots $q = 1$ and $q = \dfrac{1-p}{p}$. The extinction probability is the smaller root that is a valid probability. The second root $\tfrac{1-p}{p} = \tfrac1p - 1$ lies in $[0,1)$ only when $p > \tfrac12$, and there it is the answer; when $p \le \tfrac12$ it exceeds $1$ (or equals it), leaving $q=1$. So $$\boxed{q = \begin{cases} 1, & p \le \tfrac12,\\[1ex] \dfrac1p - 1, & p > \tfrac12.\end{cases}}$$ The threshold is exactly $p = \tfrac12$, where the expected number of offspring is $2p = 1$: at or below replacement the line is doomed, and only above it does the microbe stand a chance, with survival probability $2 - \tfrac1p$.

The computation

Encode the process itself: start with one microbe and simulate days of splitting-or-dying until the population is zero or has clearly exploded, and measure the extinction frequency against the formula.

import random
def formula(p): return 1.0 if p <= 0.5 else (1 / p) - 1
def simulate(p, trials=20000, cap=2000, seed=0):
    rng = random.Random(seed); extinct = 0
    for _ in range(trials):
        pop = 1
        while 0 < pop < cap:
            pop = sum(1 for _ in range(pop) if rng.random() < p) * 2   # survivors each double
        extinct += (pop == 0)
    return extinct / trials
for p in (0.4, 0.5, 0.6, 0.75, 0.9):
    print(f"p={p}: formula={formula(p):.4f}  simulated={simulate(p):.4f}")
# p=0.4: formula=1.0000  simulated=1.0000
# p=0.5: formula=1.0000  simulated=0.9995
# p=0.6: formula=0.6667  simulated=0.6646
# p=0.75: formula=0.3333  simulated=0.3296
# p=0.9: formula=0.1111  simulated=0.1129