Which Billiard Ball Is Rigged?

Riddler Express

You have $12$ billiard balls, identical except that one is either slightly heavier or slightly lighter than the rest; you do not know which ball, nor whether it is heavy or light. With a balance scale used only three times (equal numbers on each side), how can you find the odd ball and say whether it is heavy or light?

The Riddler, FiveThirtyEight, August 16, 2019(original post)

Solution

Three weighings give three outcomes each, so $3^3 = 27$ distinguishable results, comfortably more than the $24$ possibilities ($12$ balls $\times$ heavy or light). The art is to design the weighings so that each of the $24$ cases produces a distinct pattern of tilts. Label the balls $A_1\!-\!A_4$, $B_1\!-\!B_4$, $C_1\!-\!C_4$.

Weighing 1: $A$ versus $B$. If they balance, the odd ball is in $C$ and all of $A, B$ are known good. If they tilt, the odd ball is in $A \cup B$, and the direction narrows it: say $A$ is heavier, then either an $A$ ball is heavy or a $B$ ball is light.

If the first weighing balances (odd in $C$): weigh $C_1, C_2, C_3$ against three known-good balls. If balanced, $C_4$ is odd; one more weighing of $C_4$ against a good ball gives heavy or light. If not, the tilt direction tells you whether the odd $C$ ball is heavy or light, and weighing $C_1$ against $C_2$ pinpoints it.

If the first weighing tilts, say $A$ heavy: weigh $A_1, A_2, A_3, B_1$ against $A_4$ and three good $C$ balls. Balanced means the odd ball is among $B_2, B_3, B_4$ and is light, settled by $B_2$ versus $B_3$. The left side heavy means the odd ball is among $A_1, A_2, A_3$ and is heavy, settled by $A_1$ versus $A_2$. The right side heavy means either $B_1$ is light or $A_4$ is heavy, settled by weighing $B_1$ against a good ball. The case $B$ heavy is the mirror image.

The computation

Encode the full decision tree as a function that calls a $\textsf{weigh}$ oracle and returns its verdict, then run it against all $24$ truths (each ball, heavy and light) and confirm it is always right.

def solve(weigh):
    A, B = [0, 1, 2, 3], [4, 5, 6, 7]
    r1 = weigh(A, B)
    if r1 == 0:                                       # odd in C
        r2 = weigh([8, 9, 10], [0, 1, 2])
        if r2 == 0:
            return (11, "heavy" if weigh([11], [0]) > 0 else "light")
        heavy = r2 > 0; r3 = weigh([8], [9])
        cand = 10 if r3 == 0 else (8 if (r3 > 0) == heavy else 9)
        return (cand, "heavy" if heavy else "light")
    if r1 > 0:                                        # A heavy: A-heavy or B-light
        r2 = weigh([0, 1, 2, 4], [3, 8, 9, 10])
        if r2 == 0:
            r3 = weigh([5], [6])
            return (7 if r3 == 0 else (6 if r3 > 0 else 5), "light")
        if r2 > 0:
            r3 = weigh([0], [1])
            return (2 if r3 == 0 else (0 if r3 > 0 else 1), "heavy")
        return (4, "light") if weigh([4], [8]) < 0 else (3, "heavy")
    r2 = weigh([4, 5, 6, 0], [7, 8, 9, 10])           # B heavy (mirror)
    if r2 == 0:
        r3 = weigh([1], [2]); return (3 if r3 == 0 else (2 if r3 > 0 else 1), "light")
    if r2 > 0:
        r3 = weigh([4], [5]); return (6 if r3 == 0 else (4 if r3 > 0 else 5), "heavy")
    return (0, "light") if weigh([0], [8]) < 0 else (7, "heavy")

ok = True
for odd in range(12):
    for kind in ("heavy", "light"):
        w = {i: 1.0 for i in range(12)}; w[odd] = 1.1 if kind == "heavy" else 0.9
        def weigh(L, R, w=w):
            d = sum(w[i] for i in L) - sum(w[i] for i in R)
            return 0 if abs(d) < 1e-9 else (1 if d > 0 else -1)
        ok &= solve(weigh) == (odd, kind)
print("all 24 cases identified in 3 weighings:", ok)
# all 24 cases identified in 3 weighings: True

Every one of the $24$ cases is resolved correctly within three weighings.

Riddler Classic

In a two-player map-colouring game, Allison draws a simple closed curve (a new “country”) each turn and Bob must colour it differently from every country it borders. Allison wins when she forces Bob to use a seventh colour. How many countries must she draw? Extra credit: is there an upper limit on the number of colours Bob can be forced to use?

The Riddler, FiveThirtyEight, August 16, 2019(original post)

Status

Against optimal play by Bob, Allison needs $12$ countries to force a seventh colour (she needed $8$ to force a sixth in the earlier version of the game), and the extra credit answer is that there is no upper limit: a forcing pattern can be extended to demand arbitrarily many colours. Both answers come from explicit hand-drawn constructions and a “no limit appears to exist” growth argument rather than a rigorous derivation or a finite computation. This is the online map-colouring game encountered earlier in the archive; the four-colour theorem bounds a finished map but not what an adversary drawing curves one at a time can force.

Because the answers rest on geometric constructions whose optimality and unboundedness are argued by drawing rather than derived or exhaustively computed, the Classic is deferred from the worked-solution standard, in the same category as the earlier map-colouring instance.