The Barron Square and Four Sealed Checks

The Riddler for June 9, 2017. The Express is a quirky $4 \times 4$ “Barron Square” built from a digit-product rule; the Classic is an information-free optimal stopping problem on four sealed checks with no prior on the values. We derive the Classic carefully and note that two natural rules, “stop on the first increase” and the textbook secretary rule, tie in expected rank but differ in the chance of grabbing the largest check.

Riddler Express

There is a logic underlying which numbers go where in the square below. Crack the code and solve for $X$. $$\begin{array}{|c|c|c|c|} \hline 6 & 4 & 2 & 7 \\ \hline 4 & 2 & 0 & 5 \\ \hline 8 & 4 & X & 6 \\ \hline 8 & 6 & 4 & 8 \\ \hline \end{array}$$

The Riddler, FiveThirtyEight, June 9, 2017(original post)

Solution

Read each row and each column as a four-digit pattern: corners are single digits, and the middle two digits form a two-digit number. The rule is that the product of the corner digits equals the middle two-digit number.

Check the rule against rows already complete. Row $1$ has corners $6$ and $7$ with middle $42$, and $6 \cdot 7 = 42$. Row $2$: corners $4$ and $5$, middle $20$, and $4 \cdot 5 = 20$. Row $4$: corners $8$ and $8$, middle $64$, and $8 \cdot 8 = 64$. Now row $3$: corners $8$ and $6$, middle $4X$, and we need $8 \cdot 6 = 48$, so $X = 8$.

Cross-check with the columns. Column $1$: corners $6, 8$, middle $48$, and $6 \cdot 8 = 48$. Column $2$: corners $4, 6$, middle $24$, and $4 \cdot 6 = 24$. Column $4$: corners $7, 8$, middle $56$, and $7 \cdot 8 = 56$. Column $3$: corners $2, 4$, middle $0X$, and $2 \cdot 4 = 08$, so $X = 8$. Both directions agree. $$\boxed{\,X \;=\; 8.\,}$$

The computation

Enumerate $X \in \{0, 1, \ldots, 9\}$ and check which value satisfies both the row and the column rule simultaneously.

grid = [
    [6, 4, 2, 7],
    [4, 2, 0, 5],
    [8, 4, None, 6],
    [8, 6, 4, 8],
]

def row_ok(row):
    a, b, c, d = row
    return a * d == 10 * b + c

def col_ok(grid, j):
    return grid[0][j] * grid[3][j] == 10 * grid[1][j] + grid[2][j]

# verify all complete rows and columns follow the multiplication rule
assert row_ok(grid[0]) and row_ok(grid[1]) and row_ok(grid[3])
assert col_ok(grid, 0) and col_ok(grid, 1) and col_ok(grid, 3)

for x in range(10):
    g = [r[:] for r in grid]; g[2][2] = x
    if row_ok(g[2]) and col_ok(g, 2):
        print(f"X = {x}")
# X = 8

The unique value of $X$ consistent with both constraints prints, as required.

Riddler Classic

A table holds many sealed envelopes; each contains a distinct dollar amount, drawn from an unknown distribution. You will open at most four envelopes in sequence. After opening each, you may keep that check (ending the game) or discard it and continue. If you open the fourth envelope, you must keep its check. What strategy maximises your chances of going home with a nice payday?

The Riddler, FiveThirtyEight, June 9, 2017(original post)

Solution

The dollar values are arbitrary, so no strategy can depend on their absolute magnitudes. Whatever rule you adopt can only act on the ranks of the values seen so far. By symmetry, the four values that will appear are a uniformly random permutation of four ranks $A < B < C < D$, where $A$ is the smallest and $D$ the largest. The choice is between competing rank-only rules, scored against a chosen criterion such as “probability of ending with $D$” or “expected rank of the kept check”.

The submitter’s rule: stop on the first increase. Always open envelope $2$. If it exceeds envelope $1$, stop; otherwise open envelope $3$. If envelope $3$ exceeds envelope $2$, stop; otherwise open envelope $4$ and keep it. Enumerating the $24$ orderings, the rank of the kept check is distributed as $$\Pr(D) = \tfrac{10}{24}, \quad \Pr(C) = \tfrac{8}{24}, \quad \Pr(B) = \tfrac{5}{24}, \quad \Pr(A) = \tfrac{1}{24}.$$ This gives expected rank $\tfrac{1}{24}(10 \cdot 3 + 8 \cdot 2 + 5 \cdot 1 + 1 \cdot 0) = \tfrac{51}{24} \approx 2.125$, versus the naive baseline of $1.5$ for “keep the first check”.

The classical secretary rule. The textbook problem “maximise the chance of picking the largest of $n$ values revealed sequentially” has a known optimum: reject the first $r$ candidates, then take the first one that beats all of them. For $n = 4$ the optimal $r$ is $1$. Reject envelope $1$ and remember its value; then take the first later envelope that exceeds it (if any), otherwise keep envelope $4$.

Enumerating again: $$\Pr(D) = \tfrac{11}{24}, \quad \Pr(C) = \tfrac{7}{24}, \quad \Pr(B) = \tfrac{4}{24}, \quad \Pr(A) = \tfrac{2}{24}.$$ Expected rank is $\tfrac{1}{24}(11 \cdot 3 + 7 \cdot 2 + 4 \cdot 1 + 2 \cdot 0) = \tfrac{51}{24} \approx 2.125$, exactly the same.

Tied on expected rank, different on the headline. The two rules tie on expected rank but differ on the headline probability of grabbing $D$: the secretary rule gives $11/24 \approx 45.83\%$ versus the submitter’s $10/24 \approx 41.67\%$. Both strictly dominate the baseline of $1/4$ for “keep the first check”, and both ride the same intuition that you should not stop on a check unless you have evidence it is large.

The submitter’s rule is conceptually clean (“stop the moment things look up”) and is the rule highlighted in the official write-up; the secretary rule is the optimum for the strict “maximise $\Pr(\text{largest})$” criterion.

The computation

Enumerate all $24$ orderings of four distinct values and compute, for each of several candidate strategies, the distribution of the kept rank and the expected rank.

1. Iterate over the $24$ permutations of the ranks $(0, 1, 2, 3)$ representing the order in which envelopes are revealed.

2. For each permutation, apply the candidate strategy and record which rank is kept.

3. Aggregate counts and report the distribution, $\Pr(\text{largest})$, and expected rank.

from itertools import permutations

def stop_on_increase(p):
    if p[1] > p[0]: return p[1]
    if p[2] > p[1]: return p[2]
    return p[3]

def secretary_reject_1(p):
    cutoff = p[0]
    for x in p[1:]:
        if x > cutoff: return x
    return p[3]

def keep_first(p):
    return p[0]

def summarise(name, strat):
    c = {0:0, 1:0, 2:0, 3:0}
    for p in permutations((0,1,2,3)):
        c[strat(p)] += 1
    e_rank = sum(k * c[k] / 24 for k in c)
    print(f"{name}: dist={c}, P(D)={c[3]/24:.4f}, E={e_rank:.4f}")

summarise("keep first",              keep_first)
summarise("stop on first increase",  stop_on_increase)
summarise("reject 1, then take next record", secretary_reject_1)
# keep first: P(D)=0.2500, E=1.5000
# stop on first increase: P(D)=0.4167, E=2.1250
# reject 1, then take next record: P(D)=0.4583, E=2.1250

The enumeration confirms both non-trivial strategies tie at expected rank $51/24$ and that the secretary rule grabs the largest check with probability $11/24$ versus $10/24$ for the submitter’s rule.