How Much Will It Cost To Sniff Out The Spies?

Riddler Express

What is the next number in this series?
$9, 10, 19, 24, 31, 40, 51, 64, 79, 90, \ ?$

The Riddler, FiveThirtyEight, October 5, 2018(original post)

Solution

The first term $9$ is suggestive but the second term $10$ rules out an arithmetic sequence on the integers. The differences are $$1, \ 9, \ 5, \ 7, \ 9, \ 11, \ 13, \ 15, \ 11.$$ The $1$ and the trailing $11$ are the giveaways: integer terms displayed in a non-decimal base. Reading the terms as hexadecimal (base $16$) numerals, $$9_{16}, \ 10_{16}, \ 19_{16}, \ 24_{16}, \ 31_{16}, \ 40_{16}, \ 51_{16}, \ 64_{16}, \ 79_{16}, \ 90_{16}$$ they correspond to the decimal values $$9, \ 16, \ 25, \ 36, \ 49, \ 64, \ 81, \ 100, \ 121, \ 144.$$ The pattern is now obvious: $(n+2)^2$ for $n = 1, 2, \ldots, 10$. The next term is $13^2 = 169$, which in hexadecimal is $A9$: $$\boxed{A9.}$$ The hexadecimal letters $A,B,C,D,E,F$ stand for the decimal values $10$ through $15$, so $169 = 10 \cdot 16 + 9 = A9_{16}$.

The computation

Generate the sequence directly from $(n+2)^2$ and format each term in hexadecimal; confirm the first ten terms match and read off the eleventh.

for n in range(1, 12):
    v = (n + 2) ** 2
    print(f"n={n:2d}: decimal {v:3d} -> hex {format(v, 'X')}")

The script prints the sequence $9, 10, 19, 24, 31, 40, 51, 64, 79, 90, A9$.

Riddler Classic

The Riddler Intelligence Agency has $N$ agents, $K$ of whom are spies. You can send any subset of agents on a retreat. If every spy is present at a retreat, the spies hold a meeting; if any spy is missing, the meeting does not happen. You learn only whether the meeting happened. You know $N$ and $K$. What is the minimum number of retreats needed to guarantee you identify all $K$ spies, in the worst case? Take $N = 1024$, $K = 17$.

The Riddler, FiveThirtyEight, October 5, 2018(original post)

Solution

The question has a clean information-theoretic lower bound and a (substantially harder) constructive matching upper bound. We give the lower bound in full and report the constructive result.

Lower bound (information theory). Before any retreat, the set of possible spy configurations is the family of $K$-subsets of $\{1, \ldots, N\}$, of size $\binom{N}{K}$. Each retreat returns one bit (meeting or no meeting). After $r$ retreats the agent has seen at most $2^r$ distinct response patterns, so the strategy can distinguish at most $2^r$ spy configurations from one another. To force a unique identification in the worst case, $$2^{r} \;\ge\; \binom{N}{K} \quad \Longrightarrow \quad r \;\ge\; \left\lceil \log_2 \binom{N}{K} \right\rceil.$$ For $N = 1024$ and $K = 17$, $$\binom{1024}{17} \;\approx\; 3.68 \cdot 10^{36}, \qquad \log_2 \binom{1024}{17} \;\approx\; 121.47.$$ The minimum is at least $\lceil 121.47 \rceil = 122$ retreats.

Constructive upper bound. A specific strategy of Tim Black achieves the bound with $131$ retreats (within $9$ of optimal), and an alternative due to Thomas Swayze costs about $93 million at $1,000 per agent per retreat. A more retreat-heavy strategy by Laurent Lessard uses $191$ retreats but only $66 million in total cost. The headline answer the puzzle asks for is the lower bound:

Why $\log_2 \binom{N}{K}$ is tight in principle. The information bound is reachable when each retreat partitions the surviving possibilities into two halves of equal size. A retreat sends some subset $S \subseteq \{1, \ldots, N\}$. The response is "yes" iff the entire $K$-subset of spies sits inside $S$. The fraction of surviving spy-configurations with all spies in $S$ depends on the current knowledge state and on $|S|$. A balanced split is not always achievable for every state with the simple "send everyone in $S$" primitive, which is why the constructive upper bound exceeds $122$.

Binary-search outline. A clean (if not optimal) strategy is to identify spies one at a time by binary search.

1. Maintain a working set $W$ of agents known to contain at least one not-yet-identified spy.

2. Pick a subset $T \subseteq W$ to keep at home; send everyone except $T$.

3. If the meeting happens, every spy is outside $T$; remove $T$ from $W$.

4. If the meeting fails, at least one spy is in $T$; replace $W$ with $T$.

5. Iterate to corner an individual spy, then mark them and search for the next.

Choosing $|T|$ near $|W|/2$ gives roughly $\log_2 N$ retreats per spy, and $K \log_2 N \approx 17 \cdot 10 = 170$ retreats is the rough cost, comfortably above the information bound.

The computation

Compute $\binom{N}{K}$ exactly and confirm $\lceil \log_2 \binom{1024}{17} \rceil = 122$. Then simulate a one-spy-at-a-time binary-search strategy on a small randomised instance and confirm it never exceeds the analytical bound.

1. Compute $\binom{1024}{17}$ exactly and take $\lceil \log_2 \rceil$.

2. For each small $(N, K)$, run a binary search to identify the $K$ spies and record retreats used.

3. Confirm that the simulated cost lies between the information bound and the rough $K \log_2 N$ estimate.

import math, random

N_big, K_big = 1024, 17
nck = math.comb(N_big, K_big)
print(f"C(1024,17) = {nck}")
print(f"log2(C) = {math.log2(nck):.4f}")
print(f"min retreats (info bound) = {math.ceil(math.log2(nck))}")

def simulate(N, K, seed=0):
    rng = random.Random(seed)
    spies = set(rng.sample(range(N), K))
    found = set()
    suspects = set(range(N))
    retreats = 0
    while len(found) < K:
        W = set(suspects)
        while len(W) > 1:
            T = set(list(W)[: len(W) // 2])
            sent = (set(range(N)) - T) | found
            retreats += 1
            meeting = spies.issubset(sent)
            if meeting:
                W = W - T
            else:
                W = T
        s = W.pop()
        found.add(s)
        suspects.discard(s)
    assert found == spies
    return retreats

random.seed(0)
for N, K in [(32, 3), (64, 4), (128, 5), (256, 6)]:
    info = math.ceil(math.log2(math.comb(N, K)))
    sim = simulate(N, K)
    print(f"N={N}, K={K}: info bound {info}, binary search {sim}")

The script prints the information bound $122$ for the headline case, and for small instances the binary-search cost exceeds the information bound by a small constant, consistent with the published constructive strategies needing $\approx 9$ extra retreats at $N=1024, K=17$.