Can You Cover The Globe?

The Riddler for August 28, 2020. The Express revisits the classic rope-around-the-Earth trick, but for a sheet covering the whole sphere. The Classic asks how many games of War you would expect to play before seeing one that lasts exactly 26 turns with no “wars”.

Riddler Express

A rope around the equator, raised $1$ metre off the ground everywhere, needs only $2\pi \approx 6.28$ extra metres. Now cover the whole globe with a sheet lying flat on the ground, and raise the entire sheet $1$ metre. By how much must the sheet’s area increase? Take the Earth as a perfect sphere of radius $R = 6{,}378$ km. (Extra credit: name a place whose area is close to the answer.)

The Riddler, FiveThirtyEight, August 28, 2020(original post)

Solution

A sphere of radius $R$ has surface area $4\pi R^2$. Lifting the sheet $1$ metre everywhere wraps it on a sphere of radius $R + 1$, area $4\pi(R+1)^2$. The increase is $$\Delta A = 4\pi\big[(R+1)^2 - R^2\big] = 4\pi(2R + 1) = 8\pi R + 4\pi .$$ The leading term $8\pi R$ scales with the Earth’s radius, so unlike the rope (whose $2\pi$ is independent of $R$), the sheet’s extra area is large. With $R = 6{,}378{,}000$ m, $$\Delta A = 8\pi(6{,}378{,}000) + 4\pi \approx 1.603 \times 10^{8}\ \text{m}^2 = \boxed{160.3\ \text{km}^2}.$$ A square kilometre is a million square metres (not a thousand), so the answer is about $160$ km$^2$, a shade over $0.00003\%$ of the Earth’s surface. The country closest in size is Liechtenstein, at $160$ km$^2$.

The computation

Encode the two surface areas and subtract; the radius cancels into $8\pi R + 4\pi$.

import math
R = 6_378_000                            # metres
dA = 4 * math.pi * ((R + 1)**2 - R**2)   # 4*pi*(2R+1)
print(round(dA / 1e6, 1))                # 160.3  (square kilometres)
print(round((8 * math.pi * R + 4 * math.pi) / 1e6, 1))   # 160.3  (same)
print(round(100 * dA / (4 * math.pi * R**2), 5))         # 0.00003 percent

The sheet’s area must grow by about $160.3$ km$^2$, the size of Liechtenstein.

Riddler Classic

In War, a shuffled deck is split into two piles of $26$. Each turn both players flip their top card; the higher rank wins. If the ranks match, a mini “war” breaks out. A “perfect” game lasts exactly $26$ turns with no wars: one player wins every turn outright. Assuming a fresh shuffle before each game, how many games would you expect to play before seeing a perfect one?

The Riddler, FiveThirtyEight, August 28, 2020(original post)

Solution

Let $p$ be the probability that a single random game is perfect. Then the number of games until the first perfect one is geometric: it equals $g$ with probability $(1-p)^{g-1}p$, and its expectation is the arithmetico-geometric sum $$\sum_{g\ge 1} g\,(1-p)^{g-1}p = \frac{1}{p}.$$ So everything reduces to finding $p$.

Counting perfect games. Shuffle the $52$ cards; your pile is the first $26$, the opponent’s the last $26$, and turn $k$ pairs card $k$ with card $26+k$. A perfect game for you needs your rank strictly above theirs on all $26$ turns (no ties). Equivalently, pair the $52$ cards into $26$ unordered pairs, with no pair sharing a rank (a tie would force a war), and on each turn give the higher card to you. Every such no-tie pairing yields exactly one perfect deal once the $26$ pairs are dealt to turns ($26!$ orders), so the number of perfect deals is $26!\cdot N$, where $N$ counts no-tie pairings. Hence $$p = \frac{26!\,N}{52!}, \qquad \frac{1}{2^{26}} = \frac{26!}{52!}\cdot\frac{52!}{2^{26}26!} = \frac{26!}{52!}\cdot(\text{all pairings}),$$ so $p = \dfrac{1}{2^{26}}\cdot q$, where $q = N/(\text{all pairings})$ is the chance a random pairing has no equal-rank pair. The crude estimate $1/2^{26} \approx 1.49\times 10^{-8}$ (win $26$ coin flips) is an overestimate; the factor $q \approx 0.21$ corrects for ties.

Counting no-tie pairings. By inclusion–exclusion on the “bad” equal-rank pairs: within one rank (four suits) the number of ways to pick $j$ disjoint pairs is $1, 6, 3$ for $j = 0, 1, 2$, so across $13$ ranks the count of $k$ disjoint bad pairs is the coefficient $c_k$ of $(1 + 6x + 3x^2)^{13}$. Each choice of $k$ bad pairs leaves $52 - 2k$ cards to pair freely, in $(52-2k-1)!!$ ways: $$N = \sum_{k=0}^{26} (-1)^k\, c_k\, (52 - 2k - 1)!! .$$ This gives, exactly matching Angela Zhou’s value, $$p = \frac{93{,}686{,}147{,}409{,}122{,}073{,}121}{29{,}908{,}397{,}871{,}631{,}390{,}876{,}014{,}250{,}000} \approx 3.1324\times 10^{-9}.$$ The expected number of games until you sweep is $1/p \approx 319$ million; until either player sweeps it is half that.

The computation

Encode the count of no-tie deck pairings by inclusion–exclusion, then form $p = 26!\,N/52!$ and its reciprocal. The exact rational matches the official solution.

from math import factorial
from fractions import Fraction

def matchings(m):                  # perfect matchings of m cards = (m-1)!!
    r, m = 1, m - 1
    while m > 1:
        r *= m; m -= 2
    return r

poly = [1]                         # (1 + 6x + 3x^2)^13 ; c_k = coeff of x^k
for _ in range(13):
    new = [0] * (len(poly) + 2)
    for i, a in enumerate(poly):
        new[i] += a; new[i+1] += 6*a; new[i+2] += 3*a
    poly = new

N = sum((-1)**k * c * matchings(52 - 2*k) for k, c in enumerate(poly))
p = Fraction(N) * factorial(26) / factorial(52)
print(float(p))                    # 3.1324361743e-09
print(float(1/p), float(1/(2*p)))  # 319240343.4 ; 159620171.7
official = Fraction(29908397871631390876014250000, 93686147409122073121)
print((1/p) == official)           # True

The analytic $p$ reproduces the official exact fraction, giving about $319$ million games to win a perfect sweep yourself, or $160$ million until either player does.