Coin Parity with a Balance Scale

This puzzle comes from the amazing blog by Tanya Khovanova.

The puzzle

You have $2^n$ visually identical coins, each weighing either 10 or 11 gram. You have a standard balance that will weigh groups of coins. Your goal is to determine whether the parity of 10 gram coins (whether it is even or odd), using at most $n$ weighings.

You can start with the smaller problems trying to solve this for 4 coins with 2 weighings, 8 coins with 3 weighings, or even 16/32 coinds in 4/5 weighings respectively.

Visual Solution

The interactive media below lets you try it for $n = {3, 4, 5}$ (8, 16, and 32 coins respectively) with $n$ weighings allowed. As you might guess, the solution is effectively a binary search (glad to be grinding LeetCode right now).

Select the number of coins (8, 16, or 32) and the number of 10 Gram coins. Then click New puzzle (for a new coin assignment) and step through the weighings manually (Measure W₀ button), or hit Run auto to watch the algorithm work automatically.

Formal Solution

The argument is a discrete analogue of the intermediate value theorem: if a quantity starts positive and ends negative while changing by at most 2 each step, it must hit zero somewhere along the way — and hitting zero is exactly what a balanced scale tells us. There are three key ideas:

1. $\textbf{Reduction.}$ Checking the parity of the signed difference $D = L - R$ of any complete weighing (equal coins on each side) suffices to determine the parity of the coin count.
2. $\textbf{Binary search.}$ We construct a sequence of $m+1$ complete weighings where consecutive weighings differ by a single swapped pair, so $\lvert D_{k+1} - D_k \rvert \le 2$. The sequence starts at $D_0$ and ends at $D_m = -D_0$. And then we run a binary search for a sign change in this sequence.
3. $\textbf{Terminal condition.}$ Any balanced weighing along the binary search will conclude even parity. If none balance, two adjacent opposite-sign values must be found and I show that this forces odd parity.

Thus the decision rule is: if any weighing balances, parity is even; if none balance, parity is odd.

Notation and reduction

Let $N=2^n$. Since $N$ is even, the count of 10g coins and the count of 11g coins have the same parity (they sum to $N$), so it suffices to determine the parity of $T$, the number of 10g coins. We work only with complete weighings: those placing exactly $N/2$ coins on each pan. Let $m = N/2 = 2^{n-1}$.

Proof

Since every coin lies on exactly one pan, \(L + R = T\). Modulo 2, subtraction and addition agree, so \(D = L - R \equiv L + R = T \pmod{2}\). $\blacksquare$

In particular, a balanced weighing ($D = 0$) implies $T$ is even, and if $T$ is odd no complete weighing can ever balance.

Sequence of weighings

We will start by pairing the coins (randomly as the pairing is immaterial) into $m=2^{n-1}$ pairs $(x_1, y_1), \ldots, (x_m, y_m)$. Then, we construct a sequence of complete weighings as follows: for $k = 0, 1, \ldots, m$, define the complete weighing $W_k$ by

\[\begin{aligned} L_k &= \{y_1, \ldots, y_k,\; x_{k+1}, \ldots, x_m\} \\ R_k &= \{x_1, \ldots, x_k,\; y_{k+1}, \ldots, y_m\} \end{aligned}\]

So $W_0$ puts all $x$-coins on the left, and each step swaps one pair. For $k \in {0, 1, \ldots, m}$, denote by $D_k$ the signed weight difference of weighing $W_k$. Note that at $W_m$, the coins in each pair have swapped their position and thus: $D_m = -D_0$.

Binary search

Weigh $W_0$. If it balances, we know that $T$ is even and we are done. Otherwise $D_0 \neq 0$ and since $D_m = -D_0$ the signed differences start and end with opposite signs. Next we run a binary search through the sequence $W_0, W_1, \ldots, W_m$ as follows: Maintain an interval of indices $[a,b]$ such that $D_a$ and $D_b$ have opposite signs. Initially this is $[0,m]$. Its length is a power of two.

While $b-a>1$, let $c = (a+b)/2$ and weigh $W_c$. If $D_c=0$, then the weighing balances and the parity is even. Otherwise, $D_c$ has the same sign as exactly one of $D_a$ and $D_b$. Retain the half-interval whose endpoint values have opposite signs:

\[[a,b] \leftarrow \begin{cases} [a,c],&\text{if }D_aD_c<0,\\ [c,b],&\text{if }D_cD_b<0. \end{cases}\]

Thus each additional weighing halves the interval while preserving the opposite-sign condition.

The initial interval has length $m=2^{n-1}$. After $n-1$ midpoint weighings (plus the initial 1 weighing for $W_0$ gives a total of $n$ weighings), either a balance has occurred or the remaining interval has length $1$. In the latter case, we have adjacent indices $k$ and $k+1$ for which $D_k$ and $D_{k+1}$ are nonzero and have opposite signs.

Terminal condition

Once we find two adjacent indices with opposite weight differences, we need to show that $T$ has to be odd. Now, we know that:

\[\begin{aligned} D_{k+1} - D_k &= \bigl(\operatorname{weight}(y_{k+1}) - \operatorname{weight}(x_{k+1})\bigr) - \bigl(\operatorname{weight}(x_{k+1}) - \operatorname{weight}(y_{k+1})\bigr) \\ &= 2\bigl(\operatorname{weight}(y_{k+1}) - \operatorname{weight}(x_{k+1})\bigr) \\ &\in \{-2,\; 0,\; 2\} \end{aligned}\]

where the first equality follows from the single pair swap between $W_k, W_{k+1}$ and the last follows because each weight is 0 or 1.

We complete the proof by contradiction. Suppose $T$ were even. By Lemma 1, all $D_j$ would be even. Then $D_k$ and $D_{k+1}$ are even, nonzero, and of opposite sign, so $\lvert D_{k+1} - D_k \rvert \ge 4$. But we just established that $\lvert D_{k+1} - D_k \rvert \le 2$, a contradiction.

This completes the proof. $\blacksquare$

8 Coins solution

Below is the solution for eight coins by the above method. $n = 3$, $m = 4$, the five weighings are:

Weigh $W_0$; if unbalanced, weigh $W_2$ (the midpoint of $[0, 4]$). Based on whether $D_2$ shares the sign of $D_0$ or $D_4 = -D_0$, weigh $W_1$ or $W_3$. Three weighings suffice.