Balance-Scale Weighing Problems

You have 12 coins that look identical. Exactly one is counterfeit, and it differs in weight from the others — but you are not told whether it is heavier or lighter. You have a balance scale, which tells you only left heavier, right heavier, or balanced. In three weighings, find the fake coin and say whether it is heavy or light.

Almost everyone starts by splitting 6 against 6, and almost everyone gets stuck. Try it yourself first; the frustration is the point, because it pushes you toward the right question, which is not "what should I weigh?" but "how much can a weighing possibly tell me?"

Warm-up: 9 coins, one heavier, two weighings

Start with the easy cousin. Nine coins, exactly one is heavier, two weighings.

Split them into three groups of three: A, B, C. Weighing 1: A against B. If one side sinks, the heavy coin is in that group; if they balance, it is in C. Either way you are down to three candidates. Weighing 2: take any two of those three and weigh one against the other. If one sinks it is the fake; if they balance, it is the coin you left out.

Now count. Each weighing has three possible outcomes, so two weighings produce at most $3 \times 3 = 9$ distinguishable outcome sequences, and there were exactly 9 candidate coins. The puzzle fits perfectly — which is a strong hint that the only strategy that can work is one that splits the candidates into three equal thirds every single time. A 4-against-4 opening would waste the balanced branch, and you would run out of weighings.

The 12-coin solution, step by step

There are $12 \times 2 = 24$ possible answers and $3^3 = 27$ leaves, so it is just possible. Number the coins 1 to 12.

Weighing 1: $\{1,2,3,4\}$ against $\{5,6,7,8\}$.

Case A — they balance. The fake is among 9, 10, 11, 12, and coins 1–8 are known genuine. Weighing 2: $\{9,10,11\}$ against $\{1,2,3\}$. If it balances, coin 12 is fake; weigh 12 against 1 to learn heavy or light. If the left side sinks, one of 9, 10, 11 is heavy; weigh 9 against 10 — the heavier is the fake, or if they balance it is 11. If the left side rises, the same weighing finds the light one.

Case B — $\{1,2,3,4\}$ is heavier. Now the live possibilities are: one of 1–4 is heavy, or one of 5–8 is light. Eight possibilities, two weighings. The trick is to mix the two groups rather than split either one. Weighing 2: $\{1,2,5\}$ against $\{3,4,6\}$.

• Balanced — then 1, 2, 3, 4, 5, 6 are all genuine, so the fake is 7 or 8 and must be light. Weigh 7 against 8; the lighter one is the fake.
• Left heavier — the only stories that fit are "1 is heavy", "2 is heavy", or "6 is light". Weigh 1 against 2: the heavier one is the fake, and if they balance it is 6, light.
• Right heavier — the surviving stories are "3 is heavy", "4 is heavy", or "5 is light". Weigh 3 against 4, same logic.

Case C — $\{5,6,7,8\}$ is heavier. Mirror image of Case B with the two groups swapped.

Every branch finishes in three weighings and names both the coin and the direction.

The technique, and where it travels

Two ideas do all the work, and both are portable. Count the answers, count the outcomes. If a test has $m$ outcomes and you have $t$ tests, you can never separate more than $m^t$ cases; that is a hard floor on how many tests you need. Then build the test that comes closest to an even split, because any lopsided test wastes part of the budget.

That is why the general answer is $(3^k - 3)/2$ coins for $k$ weighings when the direction is unknown — 12 for three weighings, 39 for four. Hand yourself one extra coin known to be genuine and it rises to $(3^k - 1)/2$, or 13, because the spare lets you balance the pans in the branch where padding was impossible.

The same accounting cracks the poisoned wine bottles puzzle (each taster is a two-outcome test, so $t$ tasters cover $2^t$ bottles, and the answer is a binary encoding), twenty questions and its entropy bound, the comparison-sorting lower bound of $n\log n$, and egg drop problems where the budget is dropped eggs rather than weighings.