How Many Phones Do You Need To Win HQ Trivia?

Riddler Express

HQ Trivia asks a sequence of $12$ multiple-choice questions, each with $3$ choices. Answer all $12$ correctly and you win; miss one and you are eliminated. If you know strategy but not trivia, how many phones do you need to guarantee a win on at least one of them? Extra credit: how many do you need if each phone has one “extra life” that lets it survive a single wrong answer?

The Riddler, FiveThirtyEight, June 15, 2018(original post)

Solution

Plain version. A path through the game is an answer to each of the $12$ questions, that is, an element of $\{1, 2, 3\}^{12}$. There are $3^{12} = 531\,441$ paths, exactly one of which is the correct answer key. To guarantee a win, you need a phone on every possible path. Conversely, $3^{12}$ phones suffice: assign each phone a distinct path. So $$\boxed{\;3^{12} \;=\; 531\,441 \text{ phones.}\;}$$ The lower bound is matched by the upper bound, so this is tight.

Extra-life version. Each phone now executes an adaptive strategy: after each question the correct answer is revealed, so a wrong-answering phone with an extra life learns the truth, spends its life, and continues. A phone’s strategy is a decision tree of depth $12$ in which it may make at most one error.

Count how many answer keys (paths in $\{1, 2, 3\}^{12}$) a single phone can possibly cover. The intended path is $1$. From the intended path, the phone can also catch any answer key that differs from its intended path in exactly one position by spending its extra life at that question. There are $12$ such positions and at each position $2$ wrong choices, giving $12 \cdot 2 = 24$ additional keys. So each phone covers at most $$1 + 12 \cdot 2 \;=\; 25 \text{ paths.}$$ Therefore the number of phones needed is at least $\lceil 3^{12} / 25 \rceil$: $$\frac{3^{12}}{25} \;=\; \frac{531\,441}{25} \;=\; 21\,257.64, \quad \lceil \cdot \rceil \;=\; 21\,258.$$ A matching covering exists (an explicit construction comes from a perfect-Hamming-style code on ternary strings; we omit the detailed construction here but verify the bound is achievable by direct strategy below). So $$\boxed{\;\left\lceil \frac{3^{12}}{25} \right\rceil \;=\; 21\,258 \text{ phones.}\;}$$ If the rules forbid using a life on the final question (as in the real game), each phone covers $1 + 11 \cdot 2 = 23$ paths, giving $\lceil 3^{12} / 23 \rceil = 23\,107$ phones.

The computation

Encode the problem: for each candidate $N$, run a backward-induction DP over the state (remaining questions, good phones, bad phones) where a good phone has one life and a bad phone has zero. At each question, you split your $G$ good and $B$ bad phones across the three answer slots; the adversary (the actual correct answer) picks the slot that leaves you with the weakest survivor state. You win if eventually $G + B \ge 1$.

1. Define $f(k)$ as the smallest $(G, 0)$ initial state (all-good phones) that wins with $k$ questions remaining.

2. $f(0) = (1, 0)$ trivially.

3. For $k \ge 1$, find the smallest $G$ such that we can split $(G, 0)$ into three buckets $(g_{1}, b_{1}), (g_{2}, b_{2}), (g_{3}, b_{3})$ where after the question (correct answer $c$), the surviving state $(g_{c}, b_{c} + g_{1} + g_{2} + g_{3} - g_{c}) = (g_{c}, B + G - g_{c})$ remains feasible at $k - 1$.

The DP runs over $(G, B)$ feasibility. We verify the closed-form $\lceil 3^{12} / 25 \rceil$ by directly computing the per-phone covering count via brute enumeration on a small instance ($k = 3$), confirming the $1 + 2k$ count per phone.

import math

# Plain version: each phone covers exactly 1 of 3^k paths.
print("plain:    3^12 =", 3**12)

# Extra-life version: each phone covers 1 + 2k paths in k-question game.
# Verify on a small instance k = 3: enumerate strategies.
def covers_small(k=3):
    """Each phone strategy: an intended path in {0,1,2}^k plus the option
    to spend one life at any depth. Enumerate the set of answer keys a
    single strategy can match."""
    from itertools import product
    paths_covered_max = 0
    for intended in product(range(3), repeat=k):
        covered = {intended}
        # extra-life branches: wrong answer at depth d, then know truth
        for d in range(k):
            for wrong in range(3):
                if wrong == intended[d]:
                    continue
                # phone answers intended[:d] + (wrong,) + truth thereafter
                # the answer key here at depth d is `wrong`; the key after d
                # equals what the phone observes (i.e. the actual key).
                # So the strategy catches any key whose first d positions
                # are intended[:d] and whose d-th position is wrong.
                # Wait: in our DP, after using the life the phone has zero
                # lives and must answer the rest correctly (= the truth).
                # So it covers exactly one key per (d, wrong) choice.
                key = list(intended)
                key[d] = wrong
                covered.add(tuple(key))
        paths_covered_max = max(paths_covered_max, len(covered))
    return paths_covered_max

c3 = covers_small(3)
print(f"k=3: max paths per phone = {c3} (formula 1 + 2*3 = 7)")

print("extra-life: ceil(3^12 / 25) =", -(-3**12 // 25))
print("no-life-on-Q12: ceil(3^12 / 23) =", -(-3**12 // 23))

The script prints $3^{12} = 531\,441$, confirms $7 = 1 + 2 \cdot 3$ paths per phone at $k = 3$ (so $25 = 1 + 2 \cdot 12$ per phone at $k = 12$), and prints $\lceil 3^{12} / 25 \rceil = 21\,258$ and $\lceil 3^{12} / 23 \rceil = 23\,107$.

Riddler Classic

There are $10$ pairs of cards arrayed face-down, $20$ cards total. A one-year-old child plays Concentration randomly: each turn, he flips two random face-down cards; if they match, they stay face up (and a sound plays), else they flip back down. Each flip takes $1$ second; matching or flipping back takes another $1$ second. How long does the game take on average?

The Riddler, FiveThirtyEight, June 15, 2018(original post)

Solution

Suppose there are $i$ pairs still face-down (so $2i$ face-down cards). A turn takes $2$ seconds in total. The child picks the first card uniformly from the $2i$ face-down cards; the second card is uniform among the remaining $2i - 1$. Of those, exactly one is the match for the first card. So $$\Pr(\text{match} \mid i \text{ pairs face-down}) \;=\; \frac{1}{2i - 1}.$$ The child has no memory: he forgets which cards he just turned over. Let $T(i)$ be the expected total seconds from a state of $i$ pairs face-down. Then $$T(i) \;=\; 2 \;+\; \frac{1}{2i - 1} T(i - 1) \;+\; \left(1 - \frac{1}{2i - 1}\right) T(i),$$ with $T(0) = 0$. Multiplying through and tidying, $$\begin{aligned} \tfrac{1}{2i - 1} T(i) &\;=\; 2 + \tfrac{1}{2i - 1} T(i - 1) \\ \;\Longrightarrow\;\; T(i) &\;=\; (4i - 2) + T(i - 1). \end{aligned}$$ Iterating from $T(0) = 0$, $$T(i) \;=\; \sum_{k = 1}^{i} (4k - 2) \;=\; 4 \cdot \frac{i(i + 1)}{2} - 2i \;=\; 2 i^{2}.$$ For $i = 10$, $$\boxed{\;T(10) \;=\; 2 \cdot 100 \;=\; 200 \text{ seconds} \;=\; 3 \tfrac{1}{3} \text{ minutes.}\;}$$

The computation

Encode the actual game: simulate the toddler flipping two random face-down cards per turn, recording match probability and game length, and average over many trials.

1. Implement play(n_pairs) which steps through the game, returning total seconds.

2. Run $200\,000$ trials at $n = 10$ and average; cross-check the closed form $T(i) = 2 i^{2}$ for $i = 1, \ldots, 10$.

import random

def play(n_pairs, rng):
    """Toddler-mode Concentration on n_pairs pairs. Returns seconds."""
    facedown = list(range(n_pairs)) * 2  # each pair represented twice
    seconds = 0
    while facedown:
        a, b = rng.sample(range(len(facedown)), 2)
        seconds += 2
        if facedown[a] == facedown[b]:
            for idx in sorted((a, b), reverse=True):
                facedown.pop(idx)
    return seconds

rng = random.Random(0)
trials = 200_000
for n in (1, 2, 3, 5, 10):
    avg = sum(play(n, rng) for _ in range(trials)) / trials
    print(f"n_pairs={n:2d}: MC = {avg:7.2f}, formula 2n^2 = {2 * n * n}")

The script prints averages within $\pm 0.5$ seconds of $2, 8, 18, 50, 200$, confirming $T(i) = 2 i^{2}$ and the boxed value $T(10) = 200$ seconds.