Who Will Capture The Most James Bonds?

Riddler Express

You and your two roommates are super-villains laying spy-capturing traps for James Bond. Each villain designs and submits one trap, calibrated to a chosen capture probability $q \in [0, 1]$. The three submitted traps are placed in the villains’ lair in increasing order of effectiveness. Bond walks the lair in order; each trap independently captures him with its calibrated probability. Whoever submitted the trap that nabs Bond wins. The contest aggregates over all of Riddler Nation’s submissions: trios of submissions are drawn at random and run against millions of simulated Bonds. Design the trap most likely to be the one that catches Bond.

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

Solution

This is a participatory submission contest. The win rate of any single trap value $q$ depends entirely on the empirical distribution of every other entry submitted that week, which the column’s editor aggregates from $1{,}211$ submitted designs and then announces in the following column. Without that submitted population there is no derivable answer for the Express; the contest’s result is data, not theorem. As with the other empirical submission contests in this archive, the Express is therefore deferred.

For the record, the column’s post-aggregation winner used $q = 46.78\%$, and the cluster of best traps sat in the $45$ to $47\%$ range. The intuition is the trade-off the puzzle states: a trap whose calibrated $q$ is very high will be placed last (one of the three) and Bond may already be caught before he reaches it; a trap whose $q$ is very low may be placed first but seldom catches anybody. The optimal $q$ depends on the empirical distribution of the other two traps in the lair, which is a property of submitted entries that week.

Riddler Classic

When dealt a hand of cards, you want to sort it by suit: all cards of one suit together, and, if possible, with no two same-colour suit-blocks adjacent. You sort by moving a single contiguous block of cards to a new position, preserving the order inside the block and outside it. For a hand of $N = 6$ cards (pitch), and for general $N$ between $1$ and $13$, what is the probability you can achieve the sort in one move? Suits are spades, hearts, diamonds, clubs; spades and clubs are black, hearts and diamonds are red.

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

Solution

What matters about a hand is only the sequence of suits, since numbers are ignored. Drawing $N$ cards from a fair deck (where each suit has $13$ of the $52$ cards) and looking at the suit pattern gives a sequence $s_1 s_2 \cdots s_N$ on the alphabet $\{S, H, D, C\}$ (spades, hearts, diamonds, clubs). For $N \le 13$ the four-suit symmetric draw is well approximated by drawing each $s_i$ independently and uniformly from the four suits, since at most $13$ of $52$ cards of any suit can be drawn. The $4^N$ equally likely suit patterns will be the working sample space; the actual deck-without-replacement count produces an answer about $0.5$ percentage point lower at $N = 6$, an immaterial correction.

What counts as a sorted hand. The reader wants:

1. every suit that appears in the hand forms one contiguous block (each suit appears as a single run);

2. if it is achievable by some ordering of those suit-blocks, no two blocks of the same colour are adjacent.

Condition (2) is conditional. With three suits one black and one red, the run order $\text{black}, \text{red}, \text{black}$ avoids same-colour adjacency. With only two suits both black, no ordering avoids it, and the reader’s rule then makes any grouped sequence acceptable.

One block move. A move picks indices $i \le j$, removes the block $s_i \cdots s_j$, and re-inserts it at any of the $N - (j - i + 1) + 1$ free positions in the residual sequence. The block’s internal order is preserved. There are $\Theta(N^2)$ choices of $(i, j)$ and $O(N)$ insertion points, giving $O(N^3)$ candidate post-move sequences (a textbook count for $N = 6$ is $36$ distinct moves, for $N = 13$ it is $365$). Including “no move” adds the identity.

The probability. A suit pattern is fixable iff some block move sends it to a sorted hand. For each of the $4^N$ equally likely patterns, enumerate the candidate moves and check whether the resulting sequence satisfies the two conditions above. The fraction of fixable patterns is the answer. For $N = 6$, $2{,}528$ of the $4{,}096$ patterns are fixable, giving $$\Pr(\text{fixable} \mid N = 6) \;=\; \frac{2528}{4096} \;\approx\; 0.6172,$$ that is, about $$\boxed{61.7\%}.$$ For $N \in \{1, 2, 3, 4\}$ every pattern is already sorted or one move from sorted, so the probability is $1$. Beyond $N = 4$ it falls quickly; for a $13$-card bridge hand the probability is $\approx 0.4\%$.

The computation

Enumerate every suit pattern, every candidate block move on that pattern, and test the post-move sequence against the sorted-hand definition.

1. For $N$ from $1$ to $7$, iterate over all $4^N$ patterns on $\{S, H, D, C\}$.

2. For each pattern, generate every move (block $[i, j]$ inserted at position $k$).

3. A post-move sequence is sorted iff every appearing suit forms a single run; and either the resulting run order avoids same-colour adjacency, or no permutation of that suit set can avoid it.

4. Report the count of fixable patterns over $4^N$.

from itertools import product, permutations

COLOR = {'S': 'B', 'C': 'B', 'H': 'R', 'D': 'R'}

def runs(seq):
    out, cur = [], seq[0]
    for x in seq[1:]:
        if x != cur:
            out.append(cur); cur = x
    out.append(cur)
    return out

def is_sorted(seq):
    r = runs(seq)
    if len(set(r)) != len(r):
        return False                           # some suit appears in 2+ runs
    no_adj = lambda gs: all(
        COLOR[gs[i]] != COLOR[gs[i + 1]] for i in range(len(gs) - 1)
    )
    if no_adj(r):
        return True
    return not any(no_adj(p) for p in permutations(r))   # rule 2 unachievable

def reachable(seq):
    n = len(seq)
    out = {tuple(seq)}
    for i in range(n):
        for j in range(i, n):
            block = seq[i:j + 1]
            rest = seq[:i] + seq[j + 1:]
            for k in range(len(rest) + 1):
                out.add(tuple(rest[:k] + block + rest[k:]))
    return out

def can_fix(seq):
    return any(is_sorted(list(s)) for s in reachable(seq))

for N in range(1, 8):
    total = 4 ** N
    good = sum(1 for p in product('SHDC', repeat=N) if can_fix(list(p)))
    print(f"N={N}: {good}/{total} = {good / total:.4f}")

The script prints $1$ for $N \in \{1, 2, 3, 4\}$ and $\frac{2528}{4096} = 0.6172$ for $N = 6$, matching the boxed answer.