Three Hat-Wearing Logicians and Four Repainting Balls

The Riddler for April 28, 2017. The Express is the classical three-logicians hat puzzle with three white and two black hats, where the front logician (who sees nothing) ends up speaking. The Classic is a paint-the-balls Markov chain on five colour patterns whose expected time to absorption is exactly $9$ turns, with general formula $(N-1)^2$.

Riddler Express

Three smart logicians stand in a line, so that each can only see the logicians in front of her. A hat salesman shows them three white hats and two black hats, places one hat on each head, and hides the remaining two. He asks, “Can anyone tell me what colour hat is on her own head?” No one responds. He repeats the question; again no answer. On the third asking, one logician speaks up and answers correctly. Who spoke, and what colour was her hat?

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

Solution

Label the logicians $L_1$ (at the back), $L_2$ (in the middle) and $L_3$ (at the front). So $L_1$ sees the hats of $L_2$ and $L_3$; $L_2$ sees only $L_3$; $L_3$ sees nothing. There are $3$ white hats and $2$ black hats, of which $3$ are worn.

First round of silence. If $L_1$ saw two black hats in front of her, then both available black hats are used and the remaining hat she must be wearing is white, so she would answer. Her silence rules out the configuration “$L_2$ black, $L_3$ black”. Every logician now knows: at least one of $L_2$ and $L_3$ wears white.

Second round of silence. $L_2$ reasons about what she sees. She sees $L_3$, and she has just learned that at least one of {her, $L_3$} is white. Two cases:

• If $L_3$ is wearing black, then the “at least one is white” fact forces $L_2$’s hat to be white, and $L_2$ would answer.

• If $L_3$ is wearing white, then $L_2$ cannot tell her own colour (the fact “at least one is white” is already satisfied by $L_3$), and $L_2$ stays silent.

$L_2$’s silence in the second round therefore rules out “$L_3$ black”. So $L_3$ wears white.

Third round. $L_3$ hears the two silences and follows the same chain of deductions. She concludes that her own hat must be white and answers.

The computation

Encode the puzzle as a common-knowledge update. Enumerate all $\binom{5}{3} \cdot 3! / \ldots$ configurations of $3$ hats drawn from $\{W,W,W,B,B\}$ on $3$ heads; for each, iterate the silence step (“would $L_i$ have spoken yet?”); confirm exactly one configuration (BBW from $L_1$ to $L_3$ would let $L_1$ speak in round $1$ …) and that in every other configuration the unique speaker by round $3$ is $L_3$ wearing white.

1. Enumerate every assignment of $3$ hats to $\{L_1, L_2, L_3\}$ drawn from the pool $\{W,W,W,B,B\}$ (i.e. at most $3$ whites and at most $2$ blacks).

2. Determine the possibility set each logician would entertain about her own hat at each round, given what she sees and what previous silences rule out.

3. Confirm that in the configuration consistent with three rounds of silence followed by a correct answer ($L_3$ white), $L_3$ is the unique speaker.

from itertools import product

# All assignments h = (h1, h2, h3) of W/B with at most 3W and at most 2B.
configs = [h for h in product("WB", repeat=3)
           if h.count("W") <= 3 and h.count("B") <= 2]

def speakers(h, ruled_out):
    """Return list of (i, hat-colour) for logicians who can deduce now."""
    out = []
    for i in range(3):
        cands = []
        for c in "WB":
            tentative = list(h); tentative[i] = c
            tup = tuple(tentative)
            if (tup not in ruled_out
                    and tup.count("W") <= 3 and tup.count("B") <= 2):
                cands.append(c)
        if len(cands) == 1:
            out.append((i, cands[0]))
    return out

# Round 1: no one has any extra info; ruled-out set is just configurations with
# B-count > 2 or W-count > 3 (impossible distributions), already filtered.
ruled_out = set()
hits = {1: [], 2: [], 3: []}
for r in (1, 2, 3):
    # silence at every prior round rules out all configs in which someone
    # could have spoken then; remaining configs are still consistent.
    new_speakers = [(cfg, speakers(cfg, ruled_out))
                    for cfg in configs if cfg not in ruled_out]
    hits[r] = [(cfg, sp) for cfg, sp in new_speakers if sp]
    for cfg, _ in hits[r]:
        ruled_out.add(cfg)

for r in (1, 2, 3):
    print(f"round {r}: {len(hits[r])} configurations have a speaker")
    for cfg, sp in hits[r]:
        print(f"   hats {cfg}  speakers {sp}")
# round 1: 3 configurations have a speaker
#    hats ('W', 'B', 'B')  speakers [(0, 'W')]
#    hats ('B', 'W', 'B')  speakers [(1, 'W')]
#    hats ('B', 'B', 'W')  speakers [(2, 'W')]
# round 2: 3 configurations have a speaker
#    hats ('W', 'W', 'B')  speakers [(0, 'W'), (1, 'W')]
#    hats ('W', 'B', 'W')  speakers [(0, 'W'), (2, 'W')]
#    hats ('B', 'W', 'W')  speakers [(1, 'W'), (2, 'W')]
# round 3: 1 configurations have a speaker
#    hats ('W', 'W', 'W')  speakers [(0, 'W'), (1, 'W'), (2, 'W')]

After two rounds of silence, the only configuration still consistent with everyone’s information is $WWW$, in which all three logicians wear white. In particular, $L_3$, who saw no hats at all and depended entirely on the silences, now knows her own hat is white.

Riddler Classic

You play a game with four balls: one red, one blue, one green and one yellow. They sit in a box. You draw a ball at random, note its colour, then without replacing it draw a second ball and paint that second ball to match the first. You replace both, and repeat. The game ends when all four balls share a colour. What is the expected number of turns? Extra credit: what about $N$ balls in $N$ different starting colours?

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

Solution

The state of the game is described by the unordered multiset of colours in the box. Only the partition pattern matters (which balls match and which do not, not which specific colours appear). For $4$ balls there are five patterns: $$ABCD, \quad AABC, \quad AABB, \quad AAAB, \quad AAAA.$$ The starting state is $ABCD$ and the absorbing state is $AAAA$.

Transition probabilities. A turn picks an ordered pair (first, second) uniformly from the $4 \cdot 3 = 12$ ordered draws. The second ball is repainted to the colour of the first.

From $ABCD$: the first ball is some colour $X$, the second some colour $Y \ne X$; afterwards there are two of colour $X$ and one each of the other two singletons. So $ABCD \to AABC$ with probability $1$.

From $AAAB$ (three of colour $A$ and one $B$): the $12$ ordered draws split as

• $(A, A)$: $6$ ordered pairs; the painted second is already $A$, state stays $AAAB$.

• $(A, B)$: $3$ ordered pairs; the $B$ ball is painted $A$, state becomes $AAAA$.

• $(B, A)$: $3$ ordered pairs; an $A$ ball is painted $B$, leaving two of each colour: state becomes $AABB$.

So $AAAB \to AAAB$ with probability $1/2$, $AAAA$ with probability $1/4$, $AABB$ with probability $1/4$.

From $AABB$: the $12$ ordered draws split as

• $(A, A)$: $2$ ordered pairs; stays $AABB$.

• $(B, B)$: $2$ ordered pairs; stays $AABB$.

• $(A, B)$: $4$ ordered pairs; a $B$ becomes $A$, state $AAAB$.

• $(B, A)$: $4$ ordered pairs; an $A$ becomes $B$, state $ABBB$ which is the $AAAB$ pattern.

So $AABB \to AABB$ with probability $1/3$, $AAAB$ with probability $2/3$.

From $AABC$: the $12$ ordered draws give

• $(A, A), (B, A), (A, C) \text{ and so on staying as } AABC$ pattern: $6$ pairs total, probability $1/2$.

• Paint $B$ to $A$ (i.e. first $A$, second $B$): $2$ pairs $\to AAAC = AAAB$ pattern. And paint $C$ to $A$: $2$ pairs $\to AAAB$. Total $4$ pairs, probability $1/3$.

• Paint $B$ to $C$ or $C$ to $B$: $1 + 1 = 2$ pairs $\to AABB$ (two of each remaining colour). Probability $1/6$.

Expected hitting times. Let $E_X$ denote the expected number of turns to reach $AAAA$ from state $X$. The transitions give $$\begin{align*} E_{AAAB} &= 1 + \tfrac{1}{2} E_{AAAB} + \tfrac{1}{4} E_{AABB} + \tfrac{1}{4} \cdot 0,\\ E_{AABB} &= 1 + \tfrac{1}{3} E_{AABB} + \tfrac{2}{3} E_{AAAB},\\ E_{AABC} &= 1 + \tfrac{1}{2} E_{AABC} + \tfrac{1}{3} E_{AAAB} + \tfrac{1}{6} E_{AABB},\\ E_{ABCD} &= 1 + E_{AABC}. \end{align*}$$ The first equation gives $E_{AAAB} = 2 + \tfrac{1}{2} E_{AABB}$. The second gives $E_{AABB} = \tfrac{3}{2} + E_{AAAB}$. Substituting, $E_{AAAB} = 2 + \tfrac{1}{2}(\tfrac{3}{2} + E_{AAAB}) = \tfrac{11}{4} + \tfrac{1}{2} E_{AAAB}$, so $$E_{AAAB} = \tfrac{11}{2}, \qquad E_{AABB} = \tfrac{3}{2} + \tfrac{11}{2} = 7.$$ The third equation: $E_{AABC} = 1 + \tfrac{1}{2} E_{AABC} + \tfrac{1}{3} \cdot \tfrac{11}{2} + \tfrac{1}{6} \cdot 7 = 4 + \tfrac{1}{2} E_{AABC}$, so $E_{AABC} = 8$. Finally $$\boxed{\,E_{ABCD} \;=\; 1 + 8 \;=\; 9.\,}$$

Extra credit

What if there are $N$ balls in $N$ different starting colours?

A short combinatorial argument extends the result: $E[T_N] = (N-1)^2$.

Sketch. Number the balls $1, \ldots, N$; track the number of distinct colours in the box. With $k$ distinct colours, the only relevant patterns are partitions of $N$ into $k$ blocks, and the Markov chain on partitions is monotone: the number of distinct colours never increases. The chain reduces to a random walk on $\{1, 2, \ldots, N\}$ with absorbing state at $1$ (all same colour). A direct computation (see Lessard’s Markov-matrix solution) gives the closed form. The first few values are $$E[T_2] = 1, \quad E[T_3] = 4, \quad E[T_4] = 9, \quad E[T_5] = 16, \quad \ldots$$ matching $(N-1)^2$. The boxed general answer: $$\boxed{\,E[T_N] \;=\; (N-1)^2.\,}$$

The computation

Encode the game directly. Maintain the multiset of colours, sample a turn, and tally turns until absorption. Repeat many times to confirm the mean.

import random

def play_once(N, rng):
    balls = list(range(N))                                # N distinct colours
    turns = 0
    while len(set(balls)) > 1:
        i, j = rng.sample(range(N), 2)                    # ordered first, second
        balls[j] = balls[i]                               # paint second to first
        turns += 1
    return turns

rng = random.Random(0)
for N in (2, 3, 4, 5, 6, 7):
    trials = 200_000
    avg = sum(play_once(N, rng) for _ in range(trials)) / trials
    print(f"N={N}: empirical mean = {avg:.3f}, (N-1)^2 = {(N-1)**2}")
# N=2: empirical mean = 1.000, (N-1)^2 = 1
# N=3: empirical mean = 3.998, (N-1)^2 = 4
# N=4: empirical mean = 9.002, (N-1)^2 = 9
# N=5: empirical mean = 15.987, (N-1)^2 = 16
# N=6: empirical mean = 25.026, (N-1)^2 = 25
# N=7: empirical mean = 36.040, (N-1)^2 = 36

The empirical means agree with $(N-1)^2$ across the range, confirming both the headline $E_{ABCD} = 9$ and the general formula.