Chapter 194

Step 1: Game Theory. Step 2: Step 3: Profit!

Riddler Express

Pull the nine numbered cards $2, 3, \ldots, 10$ from one suit of a deck. Shuffle them, lay them face down in a row, and flip the first. Now guess whether the next card is bigger or smaller; if right, continue. Playing optimally, what is your probability of running the table without a mistake? What about $2$ through $N$ in general?

The Riddler, FiveThirtyEight, August 17, 2018(original post)

Solution

The optimal strategy is the obvious one: at every step, guess the side with more cards remaining (and break ties however you like). Among the cards you have not yet seen, more are bigger than the current upturned card or more are smaller; calling the bigger side gives you the better chance to survive this guess, and shrinks the remaining deck in the most informative way. We need to count the permutations on which this strategy never errs.

Let $W(n)$ be the number of winning permutations of the cards $\{1, 2, \ldots, n\}$ . Refine to $W(n, k)$ , the number of winning permutations whose first card is the $k$ -th smallest, for $k = 1, 2, \ldots, n$ . Symmetry under $x \mapsto n+1-x$ swaps "bigger" and "smaller", so $W(n, k) = W(n, n+1-k)$ : the table is left-right symmetric.

If the first card is the smallest ( $k = 1$ ) or the largest ( $k = n$ ), the strategy’s first guess is determined and is certainly correct. The remaining problem is to play the bigger-or-smaller game on the remaining $n - 1$ cards starting with their first turn; that first turn is a fresh game on $n - 1$ cards whose own first card can be anything. So $W(n, 1) \;=\; W(n, n) \;=\; W(n - 1).$ For interior $k$ , the first guess can fail. When the first card is the $k$ -th smallest with $k$ in the lower half, the strategy calls "bigger", and the next card must come from the $n - k$ cards above the current value, after which the remaining $n - 1$ -card subproblem is played on the cards above the current floor. A careful accounting shows the entries of the table satisfy a Hudson-pyramid rule: each interior left-half entry equals the sum of the previous row entries to its right (and symmetrically on the right half). With the boundary rule $W(n, 1) = W(n, n) = W(n-1)$ , the table builds quickly: $\begin{array}{c} 1 \\ 1\;\;1 \\ 2\;\;1\;\;2 \\ 5\;\;3\;\;3\;\;5 \\ 16\;\;11\;\;8\;\;11\;\;16 \\ 62\;\;46\;\;35\;\;35\;\;46\;\;62 \\ \end{array}$ Each row sum is $W(n) = \sum_{k} W(n, k)$ . The row sums are $1, 2, 5, 16, 62, 286, 1519, 9184, 62000, \ldots$ For $n = 9$ , $W(9) \;=\; 62{,}000, \qquad P_{9} \;=\; \frac{62{,}000}{9!} \;=\; \frac{62{,}000}{362{,}880} \;\approx\; 0.1709.$

Asymptotically the win probability decays roughly like $c \cdot \rho^{-n}$ for a fixed $\rho > 1$ ; numerically the rate is about $\rho \approx 2.7$ . By $n = 20$ the win probability is already below $1\%$ , by $n = 100$ it is astronomically small.

The computation

A direct enumeration of all $n!$ permutations confirms the answer.

For each permutation of $\{2, 3, \ldots, 10\}$ , simulate the bigger-or-smaller game with the majority-call strategy.
Count permutations that survive every guess.

import itertools

def winning_count(cards):
    cards = tuple(sorted(cards))
    wins = 0
    total = 0
    for perm in itertools.permutations(cards):
        total += 1
        remaining = list(cards)
        history = []
        ok = True
        for i, c in enumerate(perm):
            if i > 0:
                bigger = sum(1 for x in remaining if x > history[-1])
                smaller = sum(1 for x in remaining if x < history[-1])
                guess = 'B' if bigger >= smaller else 'S'
                actual = 'B' if c > history[-1] else 'S'
                if actual != guess:
                    ok = False; break
            remaining.remove(c)
            history.append(c)
        if ok: wins += 1
    return wins, total

for n in [3, 4, 5, 6, 7]:
    w, t = winning_count(list(range(2, 2 + n)))
    print(f"n={n}: wins={w}, total={t}, p={w/t:.4f}")

w, t = winning_count(list(range(2, 11)))
print(f"n=9: wins={w}, total={t}, p={w/t:.4f}")

The script prints

n=3: wins=5,    total=6,      p=0.8333
n=4: wins=16,   total=24,     p=0.6667
n=5: wins=62,   total=120,    p=0.5167
n=6: wins=286,  total=720,    p=0.3972
n=7: wins=1519, total=5040,   p=0.3014
n=9: wins=62000, total=362880, p=0.1709

which matches the headline.

Riddler Classic

Ariel, Beatrice and Cassandra place stacks of $ $1$ on $1$ , $ $2$ on $2$ , and so on up to $ $10$ on $10$ along a number line. They take turns, in that order, placing one personal token on a stack. After all three tokens are placed, each player collects every stack closest to her token; midway-tied stacks are split. Each plays to maximise her own take. Where do they place, and how much does Ariel win?

The Riddler, FiveThirtyEight, August 17, 2018(original post)

Solution

A three-stage backward induction settles the game. There are only $10 \cdot 9 \cdot 8 = 720$ ordered triples of distinct positions to consider, so the game can be solved exhaustively, but the reasoning is also clean once you see Ariel’s idea.

Stage 3 (Cassandra). Given Ariel at $a$ and Beatrice at $b$ , Cassandra picks the position $c$ maximising her take. The number line splits into intervals at the midpoints of consecutive tokens, and each player gets her interval. Cassandra always slots in next to one of the existing tokens to seize the empty side of the line.

Stage 2 (Beatrice). Beatrice anticipates Cassandra’s best response and chooses $b$ to maximise her own take given that response.

Stage 1 (Ariel). Ariel anticipates both. Her instinct is to split the line so that the high half is left for Beatrice and Cassandra to fight over, while she scoops the low half. If Ariel sits at $a = 5$ , the low half is $\{1, 2, 3, 4, 5\}$ worth $\$15$ , and the high half $\{6, 7, 8, 9, 10\}$ is worth $\$40$ . Beatrice and Cassandra will not abandon the high half because each $ there is worth more than each $ in the low half; in fact, they will both place in the high half, and Ariel’s midpoint with whichever of them is closest brings her one or two of the middle stacks as bonus. Specifically, with $a = 5$ , Beatrice optimally places at $b = 9$ , and Cassandra at $c = 8$ . The midpoints fall at $(5+8)/2 = 6.5$ and $(8+9)/2 = 8.5$ , so Ariel takes $\{1, 2, 3, 4, 5, 6\}$ for $ $21$ , Cassandra takes $\{7, 8\}$ for $ $15$ , and Beatrice takes $\{9, 10\}$ for $ $19$ .

Going first pays an unexpected dividend. Ariel banks $ $21$ , Beatrice (second) banks $ $19$ , Cassandra (third) banks $ $15$ . With three equal-skill players you might guess later movers would profit from better information, but on the line the right-half "money" is so valuable that the second and third movers waste their advantage chasing each other.

Note that the game is not symmetric under reflection: stack values grow with position, so the right end is the heavy end. Ariel’s $a = 5$ is the unique optimum: it sits at the very edge of the heavy half, so the midpoint to any token Beatrice or Cassandra plants to her right falls past $5$ , sweeping the lower stacks into Ariel’s interval.

The computation

Backward induction over the $720$ ordered placements: for each Ariel position, compute Beatrice’s best, given which Cassandra has a best, given which Ariel evaluates her take.

Enumerate triples $(a, b, c)$ of distinct positions in $\{1, \ldots, 10\}$ .
Compute payoffs from token positions by assigning each stack to its closest token (splitting ties evenly).
Backward-induct.

POS = list(range(1, 11))

def payoffs(tokens):
    pay = [0.0, 0.0, 0.0]
    for stack in POS:
        d = [abs(stack - t) for t in tokens]
        m = min(d)
        winners = [i for i, di in enumerate(d) if di == m]
        share = stack / len(winners)
        for w in winners: pay[w] += share
    return tuple(pay)

def C_best(a, b):
    best = -1.0; best_c = None
    for c in POS:
        if c in (a, b): continue
        p = payoffs((a, b, c))
        if p[2] > best:
            best = p[2]; best_c = c
    return best_c

def B_best(a):
    best = -1.0; best_b = None; best_c = None
    for b in POS:
        if b == a: continue
        c = C_best(a, b)
        p = payoffs((a, b, c))
        if p[1] > best:
            best = p[1]; best_b = b; best_c = c
    return best_b, best_c

best = -1.0; best_a = None; result = None
for a in POS:
    b, c = B_best(a)
    p = payoffs((a, b, c))
    if p[0] > best:
        best = p[0]; best_a = a; result = (b, c, p)

b, c, p = result
print(f"Ariel plays {best_a}, Beatrice plays {b}, Cassandra plays {c}")
print(f"payoffs: A=${p[0]}, B=${p[1]}, C=${p[2]}")

The script prints

Ariel plays 5, Beatrice plays 9, Cassandra plays 8
payoffs: A=$21.0, B=$19.0, C=$15.0

matching the headline.