Two Mysteries of the Gold Coins

The Riddler for February 24, 2017. Two balance puzzles in escalating cruelty. The Express knows the odd coin is heavier; the Classic does not even tell you the direction.

Riddler Express

You have nine gold coins, but one is impure and is known to be heavier than the others. You have a simple balance scale. How do you find the impure coin in only two weighings?

The Riddler, FiveThirtyEight, February 24, 2017(original post)

Solution

The information-theoretic floor is the place to start. There are nine possibilities for the heavy coin, and each weighing of the balance returns one of three outcomes (left tips, balance, right tips), so two weighings can distinguish at most $3 \times 3 = 9$ cases. Nine cases on the nose, so an efficient scheme should split the candidates into three equal thirds on every weighing.

Weighing 1: put coins $\{1, 2, 3\}$ on the left and $\{4, 5, 6\}$ on the right, leaving $\{7, 8, 9\}$ aside. The heavy coin is in the heavier pan if the scale tips, and in the set aside if it balances. Either way you have narrowed to a known three.

Weighing 2: take any two of those three and weigh one against the other. The heavier coin tips its side down. If they balance, the heavy coin is the one of the three you set aside. So the strategy succeeds in $$\boxed{2 \text{ weighings}}.$$

The computation

Encode the actual experiment: pick which of the nine coins is heavy, run the two-weighing procedure on it, and confirm the procedure identifies the same coin every time. We run all nine cases exhaustively.

def identify(heavy):
    w = {i: 1 for i in range(1, 10)}
    w[heavy] = 2
    def cmp(L, R):
        s = sum(w[i] for i in L) - sum(w[i] for i in R)
        return (s > 0) - (s < 0)              # +1 left heavy, -1 right heavy, 0 balance
    s1 = cmp([1, 2, 3], [4, 5, 6])
    group = {+1: [1, 2, 3], -1: [4, 5, 6], 0: [7, 8, 9]}[s1]
    a, b, c = group
    s2 = cmp([a], [b])
    return {+1: a, -1: b, 0: c}[s2]

ok = all(identify(h) == h for h in range(1, 10))
print("all 9 cases correctly identified:", ok)
# all 9 cases correctly identified: True

Riddler Classic

You now have twelve gold coins. One is fake and has a different weight, but you do not know whether it is heavier or lighter. Using the same balance scale, how do you determine the fake coin and the direction of its weight in only three weighings?

The Riddler, FiveThirtyEight, February 24, 2017(original post)

Solution

The information bound is again the right opening move. There are $24$ unknown states ($12$ coins, each possibly heavy or light) and three weighings yield $3^3 = 27$ outcomes, so a solution is just barely possible. The plan must extract close to $\log_3$ bits from every weighing, which forces each pan to contain four coins.

Weighing 1: $\{1,2,3,4\}$ vs $\{5,6,7,8\}$. If the scale balances, the fake is one of $\{9, 10, 11, 12\}$ and the direction is still unknown. Otherwise we know the fake is among the eight coins on the scale, with a side-and-direction tag: the four on the heavier pan are heavy suspects, the four on the lighter pan are light suspects.

Branch A (first weighing balances). The fake is one of $\{9, 10, 11, 12\}$, direction unknown. Weighing 2: $\{9, 10, 11\}$ vs three known-good coins, say $\{1, 2, 3\}$. If it balances, coin $12$ is the fake, and weighing 3 (coin $12$ vs $1$) reveals its direction. Otherwise three coins are isolated with a known direction (the side they sit on tells you which); weigh any two of those three against each other to pick the culprit, just as in the Express.

Branches B and C (first weighing tips). Take the tip-heavy side. The fake is one of four heavy suspects $H = \{1, 2, 3, 4\}$ or one of four light suspects $L = \{5, 6, 7, 8\}$. Weighing 2: $\{1, 2, 5\}$ on the left, $\{3, 4, 6\}$ on the right. This swaps coin $5$ across, leaves coins $7$ and $8$ off, and puts coin $6$ on the right.

• If it balances, the fake is one of the two heldout light suspects $\{7, 8\}$, and is light. Weigh $7$ against any known-good coin: the lighter side is the fake (or it balances, in which case it is coin $8$).

• If the left side tips down, the fake is $1H$, $2H$, or $6L$ (only these three causes are consistent with both first-weighing tip and second-weighing tip-left). Weighing 3: $1$ vs $2$. Equal $\Rightarrow$ $6L$; left heavier $\Rightarrow$ $1H$; right heavier $\Rightarrow$ $2H$.

• If the right side tips down, the fake is $3H$, $4H$, or $5L$, by the same logic. Weighing 3: $3$ vs $4$, with the analogous reading.

Branch C (first weighing tipped right) is the mirror of B. So the whole procedure identifies coin and direction in exactly $$\boxed{3 \text{ weighings}}.$$

The computation

Encode the procedure exactly and run it against all $24$ possible (coin, direction) states.

def identify(coin, sign):                 # sign = +1 heavy, -1 light
    w = {i: 1 for i in range(1, 13)}
    w[coin] = 1 + sign
    def cmp(L, R):
        s = sum(w[i] for i in L) - sum(w[i] for i in R)
        return (s > 0) - (s < 0)
    s1 = cmp([1, 2, 3, 4], [5, 6, 7, 8])
    if s1 == 0:                                                # Branch A
        s2 = cmp([9, 10, 11], [1, 2, 3])
        if s2 == 0:
            s3 = cmp([12], [1])
            return (12, +1 if s3 > 0 else -1)
        d = +1 if s2 > 0 else -1
        s3 = cmp([9], [10])
        if s3 == 0: return (11, d)
        return (9, d) if (s3 > 0) == (d == +1) else (10, d)
    flip = (s1 < 0)                                            # mirror B as C
    H = [5, 6, 7, 8] if flip else [1, 2, 3, 4]
    L = [1, 2, 3, 4] if flip else [5, 6, 7, 8]
    s2 = cmp([H[0], H[1], L[0]], [H[2], H[3], L[1]])
    if s2 == 0:
        s3 = cmp([L[2]], [1 if 1 not in H + L else 9])
        return (L[2], -1) if s3 < 0 else (L[3], -1)
    if s2 > 0:
        s3 = cmp([H[0]], [H[1]])
        if s3 == 0: return (L[1], -1)
        return (H[0], +1) if s3 > 0 else (H[1], +1)
    s3 = cmp([H[2]], [H[3]])
    if s3 == 0: return (L[0], -1)
    return (H[2], +1) if s3 > 0 else (H[3], +1)

ok = all(identify(c, s) == (c, s) for c in range(1, 13) for s in (+1, -1))
print("all 24 (coin, direction) cases identified:", ok)
# all 24 (coin, direction) cases identified: True