Santa Needs Some Help With Math

Riddler Express

Santa has to harness $8$ reindeer in a specific (but to him forgotten) order. Each reindeer knows its position and will grunt if placed in the right slot. Santa lists the $8$ reindeer in a random order and follows this strategy: at the first slot he tries reindeer one by one from the top of his list until one grunts; once it does, he leaves it there and goes to the second slot, again starting from the top of the (now shorter) list. Each harness attempt takes one minute. How many minutes does it take on average to harness all eight? Extra credit: is there a strategy that does better?

The Riddler, FiveThirtyEight, December 21, 2018(original post)

Solution

Number the slots $1, 2, \ldots, N$ with $N = 8$. Because Santa’s list is uniformly random, when he arrives at slot $i$ the remaining $N - i + 1$ reindeer are in a uniformly random order, and the correct one for slot $i$ is uniformly placed among them. The number of attempts to find that grunt is uniform on $\{1, 2, \ldots, N - i + 1\}$, with expectation $$\mathbb{E}[\text{attempts at slot } i] \;=\; \frac{(N - i + 1) + 1}{2} \;=\; \frac{N - i + 2}{2}.$$ By linearity, the expected total time across all $N$ slots is $$\begin{aligned} \mathbb{E}[T_{N}] &\;=\; \sum_{i = 1}^{N} \frac{N - i + 2}{2} \;=\; \frac{1}{2} \sum_{j = 2}^{N + 1} j \\ &\;=\; \frac{(N + 1)(N + 2) - 2}{4} \;=\; \frac{N (N + 3)}{4}. \end{aligned}$$ For $N = 8$: $$\mathbb{E}[T_{8}] \;=\; \frac{8 \cdot 11}{4} \;=\; 22 \text{ minutes.}$$

$$\boxed{\mathbb{E}[T_{8}] \;=\; 22 \text{ minutes; general } \mathbb{E}[T_{N}] = N(N + 3)/4.}$$

Extra credit (a better strategy?). No. The information Santa gains from a failed attempt at slot $i$ is that the reindeer he just tried is not the slot-$i$ reindeer; he already learned which reindeer is the slot-$i$ reindeer the moment one grunted. That information does not constrain which reindeer is the slot-$j$ reindeer for $j > i$. Conditional on Santa having placed the first $i$ reindeer correctly, the remaining $N - i$ reindeer are a uniformly random permutation over the remaining $N - i$ slots, regardless of the order in which he tried earlier ones. So no reordering of his subsequent attempts changes the expected cost at any slot, and the expected total stays at $N (N + 3) / 4$.

This conclusion is sharp under the uniform-prior model. Different models (for example, Santa choosing his initial list non-uniformly, or some reindeer being more memorable than others) might shift the answer; under the puzzle as stated, $22$ minutes is the best Santa can do on average.

The computation

Simulate Santa’s strategy directly and compare against the closed form $N(N + 3)/4$.

1. Sample a uniformly random permutation as Santa’s initial list.

2. For each slot $1, \ldots, N$ in order, scan the remaining reindeer until the correct one grunts.

3. Record total attempts and average across many trials.

import random
from statistics import mean

def santa(N, trials=200_000, seed=0):
    rng = random.Random(seed)
    totals = []
    for _ in range(trials):
        perm = list(range(N))
        rng.shuffle(perm)
        remaining = perm[:]
        cost = 0
        for slot in range(N):
            for k, r in enumerate(remaining):
                cost += 1
                if r == slot:
                    remaining.pop(k)
                    break
        totals.append(cost)
    return mean(totals)

for N in (3, 5, 8, 10):
    closed = N * (N + 3) / 4
    print(f"N={N}: simulated={santa(N):.3f}, closed={closed:.3f}")

The script prints simulated averages within $0.01$ of the closed-form $N (N + 3) / 4$ for each $N$, with the headline $N = 8$ giving $22$ minutes exactly.

Riddler Classic

During one shift in Santa’s workshop, elves hear $100$ songs chosen uniformly at random with replacement from a playlist of $X$ songs. The cranky elf throws snowballs whenever the same song plays twice in a shift; this has happened during about half of the shifts. How large is the playlist?

The Riddler, FiveThirtyEight, December 21, 2018(original post)

Solution

This is the birthday problem with playlist size $X$ replacing $365$ and shift length $100$ replacing party size $23$.

Setup. The probability that a $100$-song shift has no repeat is $$Q(X) \;=\; \prod_{k = 0}^{99} \frac{X - k}{X} \;=\; \frac{X!}{X^{100} (X - 100)!}.$$ The probability of at least one repeat is $1 - Q(X)$. Cranky throws snowballs about half the time, so $1 - Q(X) = \tfrac{1}{2}$, i.e. $$Q(X) \;=\; \tfrac{1}{2}.$$

Solving for $X$. The function $Q$ is strictly increasing in $X$ (more songs means more spread), so a unique $X$ (up to integer rounding) gives $Q(X) = \tfrac{1}{2}$. Apply $\log$: $$\log Q(X) \;=\; \sum_{k = 0}^{99} \log\!\left(1 - \frac{k}{X}\right) \;\approx\; -\sum_{k = 0}^{99} \frac{k}{X} - \frac{1}{2} \sum_{k = 0}^{99} \frac{k^{2}}{X^{2}}.$$ The leading-order Taylor expansion gives $$\log Q(X) \;\approx\; -\frac{n (n - 1)}{2 X}, \quad n = 100,$$ so $Q(X) \approx \tfrac{1}{2}$ at $X \approx n (n - 1) / (2 \log 2) = 9900 / 1.3863 \approx 7141$. The constant-correction from the next Taylor term lifts the answer slightly; a numerical search for the integer crossing gives $$X \;=\; 7175.$$ At $X = 7175$, $Q \approx 0.50002$; at $X = 7174$, $Q \approx 0.49997$.

$$\boxed{X \;=\; 7{,}175 \text{ songs.}}$$

The computation

Compute $\log Q(X) = \sum_{k = 0}^{99} \log\!\big( (X - k) / X \big)$ in floats and binary-search for the integer $X$ at which $Q$ crosses $\tfrac{1}{2}$.

1. For each candidate $X$, compute $Q(X)$ by summing $100$ logarithms.

2. Binary-search over $X \in [100, 100{,}000]$ for the crossing of $Q = \tfrac{1}{2}$.

3. Confirm by evaluating $Q$ at the answer and the answer minus one.

import math

def Q(X, n=100):
    return math.exp(sum(math.log((X - k) / X)
                        for k in range(n)))

lo, hi = 100, 100_000
while hi - lo > 1:
    mid = (lo + hi) // 2
    if Q(mid) < 0.5:
        lo = mid
    else:
        hi = mid

print(f"X = {hi}: Q(X) = {Q(hi):.6f}")
print(f"X = {lo}: Q(X) = {Q(lo):.6f}")
print(f"Crossing X = {hi}")

The script prints $X = 7{,}175$ with $Q(7175) \approx 0.50002$ and $Q(7174) \approx 0.49997$, matching the boxed answer.