One Small Step For Man, One Giant Coin Flip For Mankind

Riddler Express

A soccer coach builds a team of $11$ players from an infinite pool. Each player’s jersey wears a unique positive integer; that integer is the average number of games it takes that player to score a goal. The coach wants his team to average exactly two goals per game and wants his weakest player to be as strong as possible. What number does the ideal weakest player wear? What numbers are on the other ten?

The Riddler, FiveThirtyEight, May 24, 2019(original post)

Solution

A player numbered $n$ scores $\tfrac{1}{n}$ goals per game on average. The team’s goals per game is therefore the sum of reciprocals of eleven distinct positive integers, which must equal $2$. Making the weakest player as strong as possible means minimising the largest integer on the team.

The problem is the Egyptian-fraction representation of $2$ as a sum of eleven distinct unit fractions, with the largest denominator minimised.

Setup and search. Let $M$ be the largest integer on the team. The reciprocals $1/1, 1/2, \ldots, 1/M$ have $\binom{M}{11}$ size-$11$ subsets to scan; we look for the smallest $M$ that admits a subset summing to exactly $2$. An exhaustive search from $M = 11$ upward gives the smallest such $M$:

No valid team for $M \le 23$. A direct enumeration of all $\binom{M}{11}$ subsets for $M = 11, 12, \ldots, 23$ finds none whose reciprocals sum to exactly $2$.

Unique team for $M = 24$. The first solvable case has $M = 24$, and the subset is $$\{1, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24\}.$$ Verifying: $$\begin{aligned} & \tfrac{1}{1} + \tfrac{1}{5} + \tfrac{1}{6} + \tfrac{1}{8} + \tfrac{1}{9} + \tfrac{1}{10} \\ & \quad + \tfrac{1}{12} + \tfrac{1}{15} + \tfrac{1}{18} + \tfrac{1}{20} + \tfrac{1}{24} \;=\; 2. \end{aligned}$$ A common-denominator check at $\mathrm{lcm}(1, 5, 6, \ldots, 24) = 360$ confirms the sum is $720/360 = 2$.

The numerical coincidence that $1 + \tfrac{1}{5} + \tfrac{1}{6} + \cdots + \tfrac{1}{24} = 2$ has no slick proof I know; it is one of those facts about Egyptian fractions that drop out of search.

The computation

Brute-force every size-$11$ subset of $\{1, \ldots, M\}$ in rational arithmetic, sweeping $M$ from $11$ upward; the first $M$ with a solution is the answer, and the subset itself is the team.

1. For each $M$ from $11$ upward, iterate over all $\binom{M}{11}$ subsets.

2. Compute the exact sum of reciprocals using Fraction arithmetic.

3. Stop at the first $M$ with a valid solution and print all solutions at that $M$.

from fractions import Fraction
from itertools import combinations

target = Fraction(2)
for M in range(11, 30):
    found = []
    for combo in combinations(range(1, M + 1), 11):
        if sum(Fraction(1, n) for n in combo) == target:
            found.append(combo)
    if found:
        print(f"smallest M = {M}: {len(found)} solution(s)")
        for s in found:
            print(" ", s)
        break

The script prints $$M = 24, \quad \{1, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24\},$$ the unique team realising the boxed answer.

Riddler Classic

Three astronauts will land on Mars and want to pick which of them takes the first step by a fair and efficient method. Can they make the choice using a fixed number of flips of an unfair coin? They may set the coin’s probability of heads to any number between $0$ and $1$, may choose any fixed number of flips, and may assign any combination of outcomes to each astronaut. Extra credit: five astronauts.

The Riddler, FiveThirtyEight, May 24, 2019(original post)

Solution

Yes, it is possible. The trick is to lean on the symmetry between heads and tails so that two of the three astronauts have identically distributed outcomes by construction; that leaves one continuous parameter, the coin’s heads probability $p$, and one continuous equation to solve.

The construction. Use $n = 4$ flips and assign outcomes by their number of heads. There is $1$ outcome with $4$ heads (HHHH), $4$ outcomes with $3$ heads (HHHT and its three rotations), $6$ with $2$ heads, $4$ with $1$ head, and $1$ with $0$ heads, totalling $16$ outcomes. Write this pattern as $[1, 4, 6, 4, 1]$.

Assign Astronaut A the outcomes $\{HHHH, TTTT\}$, i.e., pattern $[1, 0, 0, 0, 1]$. Assign Astronauts B and C identically: each gets pattern $[0, 2, 3, 2, 0]$, splitting the remaining outcomes symmetrically by number of heads. The full assignment $A + B + C = [1, 4, 6, 4, 1]$ uses every outcome exactly once.

By construction B and C have the same probability of winning, whatever $p$ is, because their outcome-sets are heads-tails mirrors of each other. So we only need to find $p$ with $$P_{A}(p) \;=\; p^{4} + (1 - p)^{4} \;=\; \tfrac{1}{3}.$$

Solving for $p$. The function $p^{4} + (1 - p)^{4}$ is convex in $p$ on $[0, 1]$ with value $1$ at the endpoints, minimum $\tfrac{1}{8}$ at $p = \tfrac{1}{2}$. It crosses $\tfrac{1}{3}$ at two symmetric values $p$ and $1 - p$. Setting $$p^{4} + (1 - p)^{4} \;=\; \tfrac{1}{3}$$ expands to a quartic; one closed form is $$p \;=\; \tfrac{\sqrt{3}}{6}\Bigl(\sqrt{3} - \sqrt{4 \sqrt{6} - 9}\Bigr) \;\approx\; 0.24213.$$ At this $p$ Astronaut A wins with probability $\tfrac{1}{3}$, and B and C each win with probability $\tfrac{1}{3}$ by symmetry.

Why fewer flips will not work. With $n = 1$ flip there are only $2$ outcomes; no partition into three non-empty groups exists. With $n = 2$ flips, outcome weights are $p^{2}, p(1-p), p(1-p), (1-p)^{2}$, total $1$. Their pairwise sums must give three equal thirds: $p^{2}, p(1-p), p(1-p) + (1-p)^{2}$ or rearrangements. The system is overdetermined and admits no solution with $p \in (0, 1)$. With $n = 3$ flips, the symmetric-split construction requires $A$ to take HHH and TTT, leaving $6$ outcomes for B and C; the resulting equation $p^{3} + (1-p)^{3} = \tfrac{1}{3}$ has no solution in $(0, 1)$ since $p^{3} + (1-p)^{3} \ge \tfrac{1}{4}$ on $(0, 1)$ with minimum $\tfrac{1}{4}$ at $p = \tfrac{1}{2}$.

Extra credit: five astronauts. The same symmetry trick scales. With $n = 8$ flips and $p \approx 0.81716$, Zach Wissner-Gross’s construction divides the $256$ outcomes into five sets, each summing to $\tfrac{1}{5}$. The full assignment is intricate (see the official) but the existence is guaranteed by the same continuity-and-symmetry argument: we have enough free outcome groupings at $n = 8$, and one continuous parameter $p$, to satisfy the four independent equations $P_{A} = P_{B} = P_{C} = P_{D} = P_{E} = \tfrac{1}{5}$ via $\ge 4$ symmetry reductions.

The computation

Re-encode the problem at $n = 4$: enumerate all $16$ outcomes by number of heads, compute the probability each astronaut wins under the published assignment as a function of $p$, and verify that $p \approx 0.24213$ makes all three equal to $\tfrac{1}{3}$. A direct Monte Carlo at that $p$ must also produce three counts each close to $1/3$ of the trials.

1. Build the $5$-element “number-of-heads” distribution $\binom{4}{k} p^{k} (1-p)^{4-k}$.

2. Compute Astronaut A’s win probability as the $k = 0$ plus $k = 4$ entries.

3. Solve $P_{A}(p) = \tfrac{1}{3}$ numerically by bisection.

4. Monte-Carlo the four-flip experiment at the solved $p$ over $10^{6}$ trials.

import random
from math import comb

def PA(p):
    return p ** 4 + (1 - p) ** 4

# Bisect on (0, 1/2) for the lower root.
lo, hi = 0.0, 0.5
for _ in range(80):
    mid = (lo + hi) / 2
    if PA(mid) > 1 / 3:
        lo = mid
    else:
        hi = mid
p_star = (lo + hi) / 2
print(f"p* = {p_star:.6f}, P_A(p*) = {PA(p_star):.6f}")

# Verify all three astronauts get exactly 1/3 at p*.
P_total = sum(comb(4, k) * p_star ** k * (1 - p_star) ** (4 - k)
              for k in range(5))
print(f"sum of all 16 outcomes' probs = {P_total:.6f}")

# Outcome counts B and C should match, equal to (1 - PA)/2.
PB = (1 - PA(p_star)) / 2
print(f"P_A = {PA(p_star):.6f}, P_B = P_C = {PB:.6f}")

# Build the canonical [0, 2, 3, 2, 0] / [0, 2, 3, 2, 0] split: B and C
# each get 2 outcomes with k=1, 3 with k=2, 2 with k=3. The lex-smallest
# half of each k-stratum goes to B, the rest to C.
from itertools import combinations
B_set, C_set = set(), set()
need = {1: 2, 2: 3, 3: 2}
for k in (1, 2, 3):
    outcomes = sorted(combinations(range(4), k))      # bit positions of heads
    for i, bits in enumerate(outcomes):
        out = tuple(1 if j in bits else 0 for j in range(4))
        (B_set if i < need[k] else C_set).add(out)
print(f"|B|={len(B_set)} |C|={len(C_set)}")
PB_exact = sum(p_star ** sum(o) * (1 - p_star) ** (4 - sum(o)) for o in B_set)
PC_exact = sum(p_star ** sum(o) * (1 - p_star) ** (4 - sum(o)) for o in C_set)
print(f"P_A = {PA(p_star):.6f}, P_B = {PB_exact:.6f}, P_C = {PC_exact:.6f}")

random.seed(2019)
trials = 1_000_000
def flip4():
    return tuple(1 if random.random() < p_star else 0 for _ in range(4))

def winner(out):
    k = sum(out)
    if k == 4 or k == 0:
        return "A"
    return "B" if out in B_set else "C"

counts = {"A": 0, "B": 0, "C": 0}
for _ in range(trials):
    counts[winner(flip4())] += 1
for kk, v in counts.items():
    print(f"  {kk}: {v/trials:.4f}")

The script prints $p^{*} \approx 0.242131$, $P_{A}(p^{*}) = \tfrac{1}{3}$ to the displayed precision, $P_{B}$ and $P_{C}$ within $\tfrac{1}{3}$ to six decimals, and Monte Carlo counts within $\pm 0.001$ of $\tfrac{1}{3}$ on each astronaut.

The split here gives each of B and C the head-count pattern $[0, 2, 3, 2, 0]$ across the five number-of-heads buckets; their win probabilities are equal as polynomials in $p$, by direct expansion. Note that $P_{B}$ and $P_{C}$ will not in general be equal for splits with different head-count patterns, even though the splits use heads-tails complements.