Four Puzzles From Riddler Nation’s Students

To mark the 100th Riddler column, FiveThirtyEight handed the puzzles over to maths students. Four puzzles were posed: a handshake-arrangement count, a where-does-the-extra-digit-go riddle, an optional-skip standardised test, and an image-based cornucopia grid. The cornucopia (Riddle 4) depends on an image-only chart of leaves, pumpkins, apples, candy corn, and acorns whose pixel-level values are not recoverable from the corpus; it is deferred, consistent with the rest of this volume’s image-blocked puzzles. The three derivable puzzles follow.

Riddle 1

Six knights sit at a round table and must complete a greeting ceremony: every member shakes hands with every other member exactly once. During each round of handshakes, every member must be shaking exactly one hand, and arms may not cross. Between rounds, the seating may be rearranged. What is the minimum number of seating arrangements needed for six knights? Eight knights? $N$ knights?

The Riddler, FiveThirtyEight, November 17, 2017(original post)

Solution

The answer is $\lceil \log_2 N\rceil$ arrangements, and $N$ must be even.

The non-crossing rule forces a bipartite cover. Each seating arrangement partitions the knights into two halves (those on the left of the table and those on the right). Within one arrangement, a single “round” of handshakes is a non-crossing perfect matching, but the problem allows many rounds in the same arrangement (no rearranging in between): we can keep handshaking until every left–right pair has shaken hands, since the chords between left and right knights can be enumerated in $N/2$ successive non-crossing matchings ($K_{N/2,N/2}$ has a $1$-factorisation). So one arrangement covers exactly the pairs that span its two halves.

A cover of the complete graph $K_N$ by complete bipartite subgraphs is what we need; the minimum number is the biclique cover number of $K_N$. The Graham–Pollak theorem says this number equals $\lceil \log_2 N\rceil$.

The construction. Label the $N$ knights $0, 1, \dots, N - 1$ and view labels in binary. For $r = 0, 1, \dots, \lceil \log_2 N\rceil - 1$, the $r$th arrangement seats knights with bit $r$ equal to $0$ on the left and bit $r$ equal to $1$ on the right. Every pair of distinct knights differs in at least one bit, so each pair sits left–right in at least one arrangement and shakes hands then.

The lower bound. Pick any knight, call her $K$. In one arrangement $K$ shakes hands with everyone on the opposite side, namely $N/2$ knights, so the count of knights she has not yet shaken with falls by at most a factor of two each arrangement (from $N - 1$ to $\lceil (N-1)/2\rceil$, etc.). She needs to reach $0$, so the number of arrangements is at least $\lceil \log_2 N\rceil$.

For $N = 6$ and $N = 8$: $\lceil \log_2 6\rceil = \lceil \log_2 8\rceil = 3$.

The computation

For each $N \in \{2, 4, 6, 8, 10, 12, 14, 16\}$ build the binary bipartition cover, enumerate every (left, right) pair within each arrangement, and check that every distinct $\{i, j\}$ has been covered.

1. For each arrangement $r = 0, \dots, \lceil \log_2 N\rceil - 1$, partition knights by bit $r$ of their label.

2. Within one arrangement, every (left, right) pair shakes hands at some point.

3. Aggregate across arrangements and confirm full pairwise coverage.

from math import ceil, log2

def covered_pairs(N):
    R = ceil(log2(N))
    pairs = set()
    for r in range(R):
        bit = 1 << r
        L = [j for j in range(N) if (j & bit) == 0]
        R_ = [j for j in range(N) if (j & bit) != 0]
        for a in L:
            for b in R_:
                pairs.add(frozenset((a, b)))
    return R, pairs

for N in (2, 4, 6, 8, 10, 12, 14, 16):
    R, pairs = covered_pairs(N)
    needed = N * (N - 1) // 2
    print(N, "rounds =", R, "covers", len(pairs), "of", needed,
          "ok =", len(pairs) == needed)

For every even $N$ in the sweep, the construction covers all $\binom{N}{2}$ pairs using exactly $\lceil \log_2 N\rceil$ arrangements, matching the lower bound.

Riddle 2

In Kevin’s number system, the digit keleven (an integer that lies between two other single-digit integers) is inserted somewhere along the number line. Other than this insertion, all digits remain in the usual order. Two calculations found in Kevin’s notes: $$853 + 520 = 1473, \qquad 41 \times 26 = 976.$$ Where does keleven belong?

The Riddler, FiveThirtyEight, November 17, 2017(original post)

Solution

There are $11$ single-digit symbols (the usual ten plus keleven), so Kevin’s system is base-$11$. Inserting keleven $K$ between digit symbols $d$ and $d+1$ (in the usual $0, 1, \dots, 9$ ordering) gives a digit ordering $$0, 1, \dots, d,\ K,\ d+1, \dots, 9,$$ and the symbol-to-value map is: symbols $0, 1, \dots, d$ keep their face values $0, \dots, d$; the symbol $K$ has value $d + 1$; the symbols $d+1, d+2, \dots, 9$ have values $d+2, d+3, \dots, 10$.

Test $K$ between $4$ and $5$. Then the symbol-to-value map is $5 \mapsto 6,\ 6 \mapsto 7,\ 7 \mapsto 8,\ 8 \mapsto 9,\ 9 \mapsto 10$, with $0, 1, 2, 3, 4$ unchanged.

The keleven string “853” has digit values $9, 6, 3$, so as a base-$11$ number, $$9 \cdot 121 + 6 \cdot 11 + 3 = 1089 + 66 + 3 = 1158.$$ “520” has digit values $6, 2, 0$, so $$6 \cdot 121 + 2 \cdot 11 + 0 = 748.$$ Their sum is $1906$. Convert $1906$ to base-$11$: $1906 = 1 \cdot 11^3 + 4 \cdot 11^2 + 8 \cdot 11 + 3$. Digit values $1, 4, 8, 3$, which as keleven symbols are $1, 4, 7, 3$ (since $8$ as a value writes as the symbol $7$). The base-$11$ representation is “$1473$.” Match.

Check the multiplication. “41” = $4 \cdot 11 + 1 = 45$; “26” has digit values $2, 7$, so $2 \cdot 11 + 7 = 29$; their product is $45 \cdot 29 = 1305$. In base-$11$, $1305 = 10 \cdot 121 + 8 \cdot 11 + 7$, digit values $10, 8, 7$, which in keleven symbols are $9, 7, 6$. The base-$11$ representation is “$976$.” Match.

$$\boxed{\,\text{Keleven lies between } 4 \text{ and } 5.\,}$$

A short argument why this is the unique answer: the first equation gives $8 + 5 = 13$ in keleven, but the displayed result reads “$1473$,” i.e. a $1$ then a $4$ in the hundreds. So the hundreds-place sum, base-$10$, equals $14$ ($1\cdot 11 + 4 -$ carries) or $15$. This rules out $K$ between $\le 3$ and $\ge 6$, narrowing to $K \in \{4, 5\}$. The tens digit “$7$” read against the keleven addition then forces $K$ between $4$ and $5$.

The computation

Sweep $K$’s position from $0$ to $9$; check both equations for each candidate.

1. For each insertion point $d$, build the symbol-to-value map.

2. Convert each keleven string to its base-$10$ value; compute sum and product.

3. Convert the answer back to base-$11$ digit values, then to keleven symbols.

4. The candidate is valid only if both equations round-trip.

def sym_to_val(s, d):
    out = []
    for c in s:
        v = int(c)
        out.append(v if v <= d else v + 1)
    return out

def val_to_sym(vals, d):
    out = []
    for v in vals:
        if v == d + 1:
            out.append("K")
        else:
            out.append(str(v if v <= d else v - 1))
    return "".join(out)

def kelven_to_int(s, d):
    n = 0
    for v in sym_to_val(s, d):
        n = n * 11 + v
    return n

def int_to_kelven(n, d):
    if n == 0:
        return "0"
    vals = []
    while n > 0:
        vals.append(n % 11)
        n //= 11
    return val_to_sym(list(reversed(vals)), d)

for d in range(10):
    add_lhs = kelven_to_int("853", d) + kelven_to_int("520", d)
    mul_lhs = kelven_to_int("41", d) * kelven_to_int("26", d)
    if int_to_kelven(add_lhs, d) == "1473" and \
       int_to_kelven(mul_lhs, d) == "976":
        print("K between", d, "and", d + 1)            # 4 and 5

The sweep prints exactly one match: $K$ between $4$ and $5$.

Riddle 3

A test (SAAD) has $100$ questions, each with two bubbles. Filling in the correct bubble for question $i$ gains $i$ points; filling in the incorrect bubble loses $i$ points. The student knows after each question whether it was right or wrong (before deciding the next). A student may also skip a question: skipping scores zero and resets the next question’s value back to $1$. The second question is worth $2$ points (or $1$, if the first was skipped), and so on. What strategy maximises the expected score?

The Riddler, FiveThirtyEight, November 17, 2017(original post)

Solution

Each question is a fair Bernoulli: filling in either bubble has a $50$% chance of being right. The score on a non-skipped question is $\pm i$ with equal probability, so its expected contribution is exactly $0$. Skipping contributes $0$. Whatever strategy you adopt, by linearity of expectation, $$\mathbb{E}[\text{final score}] = \sum_{\text{actions}} \mathbb{E}[\text{score of action}] = 0.$$ No strategy can beat $\mathbb{E} = 0$. The variance, however, depends sharply on the strategy: skipping everything yields a deterministic score of $0$ (variance $0$); answering all questions has variance $\sum_{i=1}^{100} i^2 = \tfrac{100 \cdot 101 \cdot 201}{6} = 338{,}350$. From the standpoint of a rational decision maker the deterministic-zero strategy is the one to pick: same expected value, no variance.

(The official Riddler answer puts the same conclusion more colourfully: “A strange game. The only winning move is not to play.”)

The computation

Simulate any strategy and confirm the empirical mean is zero to sampling precision; sweep over a small zoo of strategies (answer all; skip the high-value tail; alternating; skip-after-loss).

1. For each strategy, simulate one test by deciding (per question) to answer or skip and tossing a fair coin for correctness on answered questions.

2. Track running points: $+v$ on a correct answer of current-value $v$, $-v$ on incorrect, $0$ on skip (and reset $v$ to $1$).

3. Average the final scores over many runs.

import random

def run_test(strategy, seed):
    rng = random.Random(seed)
    v, score = 1, 0
    for q in range(100):
        skip = strategy(q, v, score)
        if skip:
            v = 1
            continue
        win = rng.random() < 0.5
        score += v if win else -v
        v += 1
    return score

def s_answer_all(q, v, s): return False
def s_skip_all(q, v, s):   return True
def s_skip_after_loss(q, v, s):
    return v > 1 and s < 0

for name, S in [("all", s_answer_all), ("skip", s_skip_all),
                ("after_loss", s_skip_after_loss)]:
    N = 20_000
    mean = sum(run_test(S, k) for k in range(N)) / N
    print(name, "mean =", round(mean, 2))           # ~ 0

Every strategy averages close to zero; only skipping every question achieves it deterministically.