How Many Earthlings Would Survive 63 Thanos Snaps?

Riddler Express

Thanos, the all-powerful supervillain, can snap his fingers and destroy half of all the beings in the universe. What if there were $63$ Thanoses, each snapping his fingers one after the other? Out of $7.5$ billion people on Earth, how many can we expect to survive? If there were $N$ Thanoses, what would the survival fraction be?

The Riddler, FiveThirtyEight, April 26, 2019(original post)

Solution

The wording matters. A snap destroys “half of all the beings in the universe,” and the other Thanoses are beings too. So each snap halves both the human population and the surviving Thanoses, which means later Thanoses may never get to snap. That is what makes the answer interesting.

Setup. Each surviving being (human or Thanos) survives an individual snap independently with probability $\tfrac{1}{2}$. Let $f(N)$ be the expected fraction of humans who survive when the queue starts with $N$ Thanoses. The first Thanos snaps; every human survives with probability $\tfrac{1}{2}$, so the population is multiplied by $\tfrac{1}{2}$ in expectation. After that snap, the remaining $N-1$ Thanoses have been thinned by independent fair coins, so the number of surviving Thanoses is $K \sim \mathrm{Binomial}(N-1, \tfrac{1}{2})$, and what happens next is an independent instance of the same problem with $K$ Thanoses.

Recursion. By the tower property, $$f(N) \;=\; \tfrac{1}{2} \sum_{k=0}^{N-1} \binom{N-1}{k} \tfrac{1}{2^{N-1}}\, f(k), \qquad f(0) \;=\; 1.$$ The outer $\tfrac{1}{2}$ is the first Thanos’s halving of humans; the sum averages $f$ over the random number $K$ of Thanoses left.

Small cases. $$\begin{aligned} f(1) &\;=\; \tfrac{1}{2}\, f(0) \;=\; \tfrac{1}{2}, \\ f(2) &\;=\; \tfrac{1}{2}\bigl(\tfrac{1}{2} f(0) + \tfrac{1}{2} f(1)\bigr) \;=\; \tfrac{3}{8}, \\ f(3) &\;=\; \tfrac{1}{2}\bigl(\tfrac{1}{4} f(0) + \tfrac{1}{2} f(1) + \tfrac{1}{4} f(2)\bigr) \;=\; \tfrac{19}{64}. \end{aligned}$$ Notice how $f(2) = \tfrac{3}{8} > \tfrac{1}{4}$ and $f(3) = \tfrac{19}{64} > \tfrac{1}{8}$: the extra Thanoses sometimes destroy each other before they can act, so the population fares better than the naive “halve $N$ times” guess of $2^{-N}$.

The naive number is wrong. Counting the modal number of snaps before the queue runs out (start with $N=63$; the surviving count typically halves: $63 \to 31 \to 15 \to 7 \to 3 \to 1 \to 0$, about $6$ snaps) gives the population fraction $2^{-6} = \tfrac{1}{64}$, or about $117$ million survivors. That ignores the spread of $K$. With the correct conditioning, $f(63) \approx 0.022199$, so the expected number of survivors is $$7.5 \times 10^{9} \times f(63) \;\approx\; 1.665 \times 10^{8}.$$

The computation

Re-encode the problem itself, not the recursion. Simulate the queue of Thanoses one snap at a time, with each surviving being (population unit and remaining Thanos) independently halved. The empirical fraction over many trials must match $f(N)$ to Monte Carlo precision, and an independent exact pass via the recursion must produce the same number.

1. Track the queue of remaining Thanoses and one population variable, here a count of $10^{6}$ “population atoms” for low-variance counting.

2. Pop the front Thanos; halve each surviving being independently by a $\mathrm{Binomial}(\text{count}, \tfrac{1}{2})$ draw.

3. Stop when the queue is empty; record the fraction of population atoms that survived.

4. Average across $50{,}000$ trials at $N = 63$; compare to the exact $f(63)$ from the recursion.

import random
from fractions import Fraction
from math import comb

def simulate(N, pop=1_000_000):
    thanoses = N
    alive = pop
    while thanoses >= 1:
        thanoses -= 1
        survivors_thanos = sum(1 for _ in range(thanoses) if random.random() < 0.5)
        thanoses = survivors_thanos
        # halve population by independent coin flips, via binomial
        # equivalent to: alive = Binomial(alive, 1/2)
        # use sum of independent halvings; for large alive use binomial sample
        alive = sum(1 for _ in range(alive) if random.random() < 0.5) \
                if alive < 200 else \
                _binomial_half(alive)
    return alive / pop

def _binomial_half(n):
    # sample Binomial(n, 1/2) via normal approx for large n
    import math
    mu = n / 2
    sd = math.sqrt(n / 4)
    return max(0, min(n, int(round(random.gauss(mu, sd)))))

def exact_f(N_max):
    f = {0: Fraction(1)}
    for N in range(1, N_max + 1):
        s = Fraction(0)
        for k in range(N):
            s += Fraction(comb(N - 1, k), 2 ** (N - 1)) * f[k]
        f[N] = Fraction(1, 2) * s
    return f

random.seed(2019)
N = 63
trials = 50_000
emp = sum(simulate(N) for _ in range(trials)) / trials
exact = exact_f(N)[N]
print(f"empirical f({N})  = {emp:.6f}")
print(f"exact     f({N})  = {float(exact):.6f}")
print(f"expected survivors out of 7.5e9 = {7.5e9 * float(exact):,.0f}")

print()
for N in [1, 2, 3, 5, 10, 20, 63]:
    print(f"f({N:2d}) = {float(exact_f(N)[N]):.8f}")

The script prints empirical $f(63) \approx 0.0222$ matching the exact $f(63) = 0.022199\ldots$, and a survivor count of about $166{,}492{,}281$, reproducing the boxed $\mathbf{166.5}$ million.

Riddler Classic

You and three friends are contestants on the newest edition of “Guess Your Hat.” Each of you has a hat placed on your head, one of four colors: red, yellow, blue, or green. Two of you might have the same colour. You can see everyone else’s hat but not your own, and your goal is to guess your own colour. You can’t communicate during the game but you can agree a strategy beforehand. The showrunners hear that strategy and choose the hats in the worst possible way for you. Can you guarantee that at least one of you wins? At least two?

The Riddler, FiveThirtyEight, April 26, 2019(original post)

Solution

The key move is to label the four colours by the integers $0, 1, 2, 3$ and work modulo $4$. The sum of all four hat-labels is some value $S \in \{0, 1, 2, 3\}$ (mod $4$). If everyone could agree in advance to “cover” each possible value of $S$, exactly one player would always be right.

The strategy. Assign each friend an integer $i \in \{0, 1, 2, 3\}$. Friend $i$ sees the other three hats summing to $S_{i}$ and guesses the colour $$g_{i} \;=\; (i - S_{i}) \bmod 4.$$ Friend $i$ is correct iff the actual sum of all four hats is $i \pmod 4$, because their guess plus the visible sum equals $i$.

For any choice of hats, the true sum $S \bmod 4$ is one specific value, so exactly one friend is correct. The showrunners cannot prevent that: whatever they pick, $S \bmod 4$ is something, and the matching friend wins.

Why two cannot be guaranteed. Count winners across all configurations under any deterministic strategy. Friend $i$’s guess $g_{i}$ depends only on the three hats they see, so under a uniform random assignment of hats their own hat is independent of $g_{i}$ and matches it with probability exactly $\tfrac{1}{4}$. Summing over the four friends, the expected number of winners under uniform random hats is $$4 \cdot \tfrac{1}{4} \;=\; 1.$$ If some strategy guaranteed $\ge 2$ winners on every configuration, the expectation under any distribution would be at least $2$, contradicting the value $1$ above. So there is a configuration with at most $1$ winner, and an adversary will pick it.

The argument generalises: with $N$ players and $N$ colours, labelling colours $0, \ldots, N-1$ and letting friend $i$ guess $(i - S_{i}) \bmod N$ guarantees exactly $1$ winner under adversarial play, and the same uniform-expectation argument forbids $\ge 2$.

The computation

Verify both claims exhaustively. For the four-friend, four-colour version there are $4^{4} = 256$ configurations. The modulo-$4$ strategy must yield at least one winner in every one of them, and there must be no four-friend deterministic strategy that yields at least two winners in every configuration.

1. Enumerate all $256$ hat assignments.

2. For each, count how many of the four friends guess correctly under the modulo-$4$ strategy. Check that the minimum across configurations is $1$ and the maximum is $1$ (it is exactly $1$, by construction).

3. For the impossibility, exploit linearity: under uniform random hats, $E[\text{winners}] = 1$ for any deterministic strategy. So $\min \le E \le \max$, hence $\min \le 1$. Verify on the mod-$4$ strategy and on a few other concrete strategies.

from itertools import product

COLOURS = 4
PLAYERS = 4

def mod4_guess(i, others):
    # others is a tuple of the three hats friend i can see
    s = sum(others) % COLOURS
    return (i - s) % COLOURS

def count_winners(hats, strategy):
    n = 0
    for i in range(PLAYERS):
        others = tuple(hats[j] for j in range(PLAYERS) if j != i)
        if strategy(i, others) == hats[i]:
            n += 1
    return n

configs = list(product(range(COLOURS), repeat=PLAYERS))
winners = [count_winners(h, mod4_guess) for h in configs]
print(f"configs        = {len(configs)}")
print(f"min winners    = {min(winners)}")
print(f"max winners    = {max(winners)}")
print(f"avg winners    = {sum(winners)/len(winners):.4f}")
# Try a naive "always guess 0" strategy.
naive = lambda i, others: 0
nw = [count_winners(h, naive) for h in configs]
print(f"naive min/avg  = {min(nw)}/{sum(nw)/len(nw):.4f}")

The script prints $\text{min} = \text{max} = 1$ for the modulo-$4$ strategy across all $256$ configurations, average $1.0000$, and the naive “always guess $0$” has minimum $0$ and average $1.0$ as expected.