12 Coins, 3 Weighings: Puzzle and Step-by-Step Solution
Logic & Strategy
Hard
Reported at SIG, Optiver, Citadel, IMC
The puzzle
You have 12 coins that look identical. One is counterfeit and is either slightly heavier or slightly lighter than the others; you do not know which. Using a balance scale only three times, find the counterfeit and say whether it is heavy or light.
Short answer: Weigh 1-2-3-4 against 5-6-7-8, then branch: three weighings with three outcomes each distinguish all 24 possibilities.
Step 1: Why three weighings can be enough
There are 24 possibilities: any of 12 coins, heavy or light. Each weighing has three outcomes: left heavy, right heavy, or balance. Three weighings give 3^3 = 27 outcome patterns, which is at least 24, so a solution is not ruled out. It also tells you every weighing must split the remaining possibilities close to evenly three ways.
Step 2: First weighing: 1, 2, 3, 4 against 5, 6, 7, 8
If it balances, coins 1 to 8 are genuine and the fake is among 9 to 12, heavy or light: 8 possibilities. Weigh 9, 10, 11 against 1, 2, 3, which are known genuine. If it balances, coin 12 is fake; weigh 12 against 1 to learn whether it is heavy or light. If 9-10-11 is heavy, the fake is heavy and among them: weigh 9 against 10, and the heavier is fake, or 11 if they balance. If 9-10-11 is light, do the same looking for the lighter coin.
If 1-2-3-4 is heavier than 5-6-7-8, the fake is one of 1, 2, 3, 4 heavy, or one of 5, 6, 7, 8 light: again 8 possibilities, and coins 9 to 12 are genuine. (If the right side is heavier, swap the roles.)
Step 3: Second weighing after an imbalance: 1, 2, 5 against 3, 6, 9
Trace each candidate. 1 heavy or 2 heavy makes the left heavy. 6 light also makes the left heavy. 3 heavy or 5 light makes the left light. 4 heavy, 7 light or 8 light leave it balanced.
Left heavy leaves {1H, 2H, 6L}: weigh 1 against 2; the heavier is fake, and if they balance, 6 is light. Left light leaves {3H, 5L}: weigh 3 against a genuine coin; if 3 is heavy it is the fake, otherwise 5 is light. Balanced leaves {4H, 7L, 8L}: weigh 7 against 8; the lighter is fake, and if they balance, 4 is heavy.
Every branch ends in three weighings with both the coin and its direction identified.
Step 4: The design principle
Each weighing must keep every branch at or below what the remaining weighings can resolve: at most 9 possibilities with two weighings left, at most 3 with one left. Mixing coins across the pans, and using known-genuine coins as fillers, is how you achieve those splits. With the same idea you can handle up to 13 coins in three weighings if you only need to find the fake, not its direction.
Why interviewers ask it
Start with the 27 ≥ 24 counting argument; it tells the interviewer you know why the puzzle is solvable before you solve it, and it guides every split.
Knowing the proof is half of it. Work 12 Coins, 3 Weighings interactively, then take it under a clock with the rest of the Outcry simulators.