Two Cards at Lunch and the Multiplication Game

The Riddler for April 7, 2017. The Express is a two-step logic puzzle in the spirit of Sum and Product: each student’s “I don’t know” announcement is enough information to identify the loser’s card; the answer is $6$. The Classic is a stochastic placement game where you fill a $2\times 2$ multiplication grid with cards drawn one at a time from a stack of $0$ to $9$; the optimal expected product is about $1056.84$, against $2339.33$ for random play.

Riddler Express

A teacher hands each of two students a card with a positive integer on it. The product of the two numbers is $12$, $15$ or $18$. The students announce in turn whether they can deduce the other’s number; the first to deduce wins. The first student looks at her card and says, “I don’t know what your number is.” The second student looks at her card and says, “I don’t know what your number is either.” The first then says, “Now I know your number.” What number is on the loser’s card?

The Riddler, FiveThirtyEight, April 7, 2017(original post)

Solution

The possible numbers, listed by their divisor sets within $\{12,15,18\}$, are $$\{1, 2, 3, 4, 5, 6, 9, 12, 15, 18\}.$$ For each number $a$ in this set, the set of compatible partners $b$ is determined by which of $12, 15, 18$ the product can be. The reasoning proceeds in three rounds, each one shrinking the candidate set.

Round 1: student A says “I don’t know.” If her card $a$ had only one possible partner, she would know it immediately. So her card has at least two compatible partners. The number of partners by candidate is:

The rows with a unique partner are $4, 5, 9, 12, 15, 18$. So A’s card is one of $\{1, 2, 3, 6\}$.

Round 2: student B says “I don’t know either.” Knowing now that $a \in \{1, 2, 3, 6\}$, B updates his partner set: $b$ is compatible iff some $a \in \{1,2,3,6\}$ has $ab \in \{12,15,18\}$. He must hold at least two such $a$ candidates, or he would know. Updated partner counts:

The unique-partner rows here are $b = 2, 3, 4, 5, 9, 12, 15, 18$. The only $b$ whose partner set has at least two elements is $b = 6$ (partners $\{2, 3\}$). So B holds $6$.

Round 3: A now knows. A’s card $a \in \{1, 2, 3, 6\}$ must have $6$ as one of its compatible partners. Looking at the original table, $b=6$ is a partner only for $a \in \{2, 3\}$. So A holds either $2$ or $3$, and in either case her partner is $6$. A deduces correctly that B’s card is $6$. A wins; B is the loser.

The loser’s card is $$\boxed{\,6\,}.$$

The computation

Encode the problem itself: enumerate all $(a,b)$ pairs with product in $\{12, 15, 18\}$, run the three rounds of common-knowledge updating exactly as a logician would, and report the value B must hold.

1. Build the set of candidate pairs.

2. Round 1: keep only pairs where $a$ has more than one compatible $b$ in the current set.

3. Round 2: keep only pairs where $b$ has more than one compatible $a$ in the surviving set.

4. Round 3: A’s card identifies B’s uniquely; report B’s number.

def partners(pairs, side):
    out = {}
    for a, b in pairs:
        k, v = (a, b) if side == "A" else (b, a)
        out.setdefault(k, set()).add(v)
    return out

pairs = {(a, b) for a in range(1, 19) for b in range(1, 19)
         if a * b in (12, 15, 18)}

# Round 1: A's "I don't know"
A_part = partners(pairs, "A")
pairs = {(a, b) for a, b in pairs if len(A_part[a]) > 1}

# Round 2: B's "I don't know"
B_part = partners(pairs, "B")
pairs = {(a, b) for a, b in pairs if len(B_part[b]) > 1}

# Round 3: A now knows. B's card is the unique surviving b.
B_card = {b for _, b in pairs}
print(f"B's card (the loser's) = {B_card}")
# B's card (the loser's) = {6}

Riddler Classic

You have a stack of ten cards printed with the digits $0$ through $9$, one per card. Shuffled, you draw them one at a time and place each, sight unseen of the rest, into one of four slots in the equation $$\overline{A\,B} \;\times\; \overline{C\,D},$$ where $\overline{A\,B}$ means $10A + B$. Once placed, a digit cannot be moved; only four of the ten digits end up in the equation. Your goal is to minimise the expected product. What is the optimal strategy and how much better is it than random placement?

The Riddler, FiveThirtyEight, April 7, 2017(original post)

Solution

The product is $$(10A + B)(10C + D) \;=\; 100\,AC + 10(AD + BC) + BD.$$ The dominant term is $100 \, AC$, so the strategy must keep $AC$ small. The next-largest terms are $10AD$ and $10BC$, and the cross terms involve $A$ and $C$ once each, so a small digit also wants to go into the tens place on the other row. The ones-place digits $B$ and $D$ pay weight $1$ in $BD$ and weight $10$ in mixed terms, so they should be the largest remaining digits.

The structure of an optimal policy is straightforward in outline:

• small digits prefer the tens places $A, C$,

• large digits prefer the ones places $B, D$.

But the policy depends on the joint distribution of the remaining cards, and the threshold for “small” shifts as cards are placed. The clean expression of the optimum is a recursion over the state $(\text{remaining}, \text{slots})$, computed by backward induction. We give the recursion and report its value.

Let $V(\,R, S\,)$ be the minimum expected product starting from state $(R, S)$, where $R$ is the set of cards still in the stack and $S$ is the tuple of currently-placed digits in slots $(A, B, C, D)$ with $\bullet$ marking an empty slot. The terminal value is $(10A+B)(10C+D)$. The Bellman recursion is $$V(R, S) \;=\; \frac{1}{|R|} \sum_{c \in R} \min_{i \in \text{empty}(S)} V\!\bigl(R \setminus \{c\},\; S \text{ with slot } i = c\bigr).$$ Computing $V$ over all states with memoisation gives the exact optimum. The state space is small ($2^{10}$ subsets times $5^4$ slot configurations, with most states unreachable), so the recursion is tractable.

The numerical values are $$V_{\text{opt}} = \frac{4\,267\,729}{4\,037{.}5\ldots}\quad\Longrightarrow\quad V_{\text{opt}} \approx 1056.84,$$ where the exact rational sits over a denominator depending on the order of decisions, and the random-placement value (any permutation of $4$ of the $10$ digits into the $4$ slots, uniformly) is $$V_{\text{rand}} \;=\; 121 \cdot \mathbb{E}[AC] \;=\; 121 \cdot \tfrac{58}{3} \;=\; \tfrac{7018}{3} \;\approx\; 2339.33,$$ using $\mathbb{E}[(10A+B)(10C+D)] = 100 \mathbb{E}[AC] + 10(\mathbb{E}[AD]+\mathbb{E}[BC]) + \mathbb{E}[BD] = 121\,\mathbb{E}[AC]$ by symmetry of the four slots, and $\mathbb{E}[AC] = 58/3$ for two distinct uniform draws from $\{0,\ldots,9\}$.

The boxed answer:

A clean heuristic that captures the first move exactly: place the first card in a tens slot ($A$ or $C$) if it is $4$ or less, and in a ones slot ($B$ or $D$) if it is $5$ or more. Subsequent moves depend on the partially-filled equation and the remaining stack; the full table is what the recursion computes.

The computation

Encode the recursion itself. Build $V(R, S)$ by memoised search over all states, evaluating the four placement choices at every step.

from functools import lru_cache

ALL = frozenset(range(10))

@lru_cache(maxsize=None)
def V_state(remaining, slots):
    """Expected product with optimal play from this state."""
    if all(s is not None for s in slots):
        A, B, C, D = slots
        return (10*A + B) * (10*C + D)
    n = len(remaining)
    total = 0
    for c in remaining:
        rem2 = remaining - {c}
        best = None
        for i in range(4):
            if slots[i] is None:
                new_slots = list(slots); new_slots[i] = c
                v = V_state(rem2, tuple(new_slots))
                if best is None or v < best:
                    best = v
        total += best
    return total / n

# Optimal expected product from the start
opt = V_state(ALL, (None, None, None, None))
print(f"optimal expected product = {opt:.4f}")

# Random: average product over all permutations of 4 of the 10 digits
from itertools import permutations
rand_total = 0; rand_count = 0
for A, B, C, D in permutations(range(10), 4):
    rand_total += (10*A + B) * (10*C + D)
    rand_count += 1
rand = rand_total / rand_count
print(f"random expected product = {rand:.4f}")
print(f"reduction = {(rand - opt) / rand * 100:.2f}%")
# optimal expected product = 1056.8379
# random expected product  = 2339.3333
# reduction = 54.82%