Twelve Coins, One Fake, Three Weighings

You have 12 coins, identical in appearance. Exactly one is fake — either lighter or heavier than the other 11, you're not told which — and the rest are genuine and all weigh the same. You have a balance scale (it shows left-heavier, right-heavier, or balanced) and exactly three weighings. Find the fake coin and determine whether it's heavy or light.

Before reading on, notice what makes this hard: you must design your second and third weighings before knowing the outcome of the ones before them if you want a clean, guaranteed strategy — or adapt on the fly, but either way every weighing has to work hard.

The trap: weighing coins in naive groups

The obvious first move — split into two groups of six and weigh them against each other — is a mistake. If they don't balance, you know the fake is in the heavier or lighter pan, but you have no idea which coin within six, and you've barely narrowed anything with your one weighing. The problem is you're not using the balance result efficiently: a weighing that only ever says "unbalanced, fake is somewhere in this big group" wastes most of its informational capacity.

That inequality is the whole reason 3 weighings can possibly work for 12 coins, and it tells you that a weighing which only learns "the fake is somewhere in this big group" is not tight enough; each weighing must narrow the suspects by close to a factor of 3.

Worked example: a working three-weighing strategy

Label the coins 1–12. First weighing: put 1,2,3,4 on the left pan, 5,6,7,8 on the right pan; 9,10,11,12 sit aside.

Case A — balances. The fake is among 9,10,11,12, and coins 1–8 are all genuine (a huge amount of information from one balanced weighing — this is exactly why "balanced" must count as informative, not a wasted weighing). Second weighing: weigh 9,10,11 (known-suspect) against three known-genuine coins, say 1,2,3. If it balances, coin 12 is fake — weigh it against any genuine coin in the third weighing to learn heavy or light. If 9,10,11 is heavier, the fake is among 9,10,11 and is heavy; if lighter, among 9,10,11 and is light. Either way, the third weighing puts two of the three suspects against each other: balance means the third is fake, imbalance identifies which of the two it is, consistent with the known direction.

Case B — left side (1,2,3,4) heavier. The fake is among 1,2,3,4 (candidate: heavy) or 5,6,7,8 (candidate: light) — eight suspects, each already carrying a known candidate direction, which is the informational win banked from this weighing. Second weighing: 1,2,5 against 3,4,6 (coins 7,8,9,10,11,12 sit aside).

• If it balances: none of 1,2,3,4,5,6 is fake, so the fake is 7 or 8, and it must be light (both were candidates only as "light"). Third weighing: 7 against a known-genuine coin — lighter means 7 is fake, balanced means 8 is fake (light either way).
• If the left pan (1,2,5) stays heavy: coins 3 and 4 are ruled out (if either were the heavy fake, moving it to the right pan would have made the right pan heavier, not the left), and 7,8 are ruled out (they're not on the scale at all). Only 1 (heavy), 2 (heavy), or 6 (light — a light 6 dragging its own pan down is exactly consistent with the left pan reading heavy) remain. Third weighing: 1 against 2 — heavier one is the fake (heavy); balance means 6 is fake (light).
• If the right pan (3,4,6) becomes heavier: by the same logic, 1 and 2 are ruled out, 6 is ruled out (a light 6 would have made the right pan lighter, not heavier), leaving 3 (heavy), 4 (heavy), or 5 (light — consistent with the left pan, containing 5, reading light). Third weighing: 3 against 4 — heavier one is the fake (heavy); balance means 5 is fake (light).

Every branch bottoms out in a single named coin with a known direction, using exactly three weighings total.

The transferable technique

This is the sharpest example of an information-counting lower bound married to an explicit construction: first check whether the number of possible outcomes ($3^{\text{weighings}}$) can even reach the number of possible answers (here, 24) — if it can't, no strategy exists, full stop. Then, when it can, build a strategy where every single weighing splits the remaining possibilities into roughly equal thirds, so that "balanced" is exploited just as hard as either tilt. The same two-step approach — count first, then construct a balanced-branching strategy — solves every weighing puzzle, twenty-questions-style guessing games, and any adaptive search problem where each query has a small fixed number of outcomes.