Twelve coins, three weighings.
The twelve coins puzzle: one coin is counterfeit and you do not know whether it is heavier or lighter. Find it, and its direction, with three uses of a balance scale. The counting argument that proves three is enough also proves exactly why thirteen coins cannot be done.
You are handed twelve coins that look identical. Eleven are genuine and weigh the same. One is counterfeit, and it is either heavier or lighter than a genuine coin; you are not told which. The only instrument available is a two-pan balance with no weights: place coins on each pan and it tells you whether the left is heavier, the right is heavier, or the pans balance.
Find the counterfeit coin and state whether it is heavy or light, using the balance no more than three times.
Two things make this harder than it looks. First, the unknown direction doubles the possibilities: coin 7 heavy and coin 7 light are different answers. Second, a balance is not a sorting machine. Splitting six against six tells you nothing useful, because either pan could be the one holding the fake. The puzzle is really about extracting the most information from each weighing, and that is a counting question before it is a cleverness question.
Before reaching for hints, try to answer a simpler one: how many distinct answers are there, and how many distinct outcome sequences can three weighings produce?
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
Count. There are 12 coins and 2 directions, so 24 possible answers. Each weighing has 3 outcomes, so three weighings give at most 27 distinguishable sequences. That is enough, but only if every weighing splits the remaining possibilities into three groups of nearly equal size.
Hint 2 the key move
The first weighing must be four against four, with four left off. Balanced leaves 8 possibilities (four coins, either direction). Tilted leaves 8 as well: the four on the heavy pan might be heavy, or the four on the light pan might be light. Anything other than four against four leaves one branch with more than 9 possibilities, which two weighings cannot resolve.
Hint 3 the finishing idea
After a tilt, coins that were on the balance become labelled: "possibly heavy" or "possibly light". Coins that were off the balance are now known genuine and can be used as reference weights. The second weighing should move coins between pans so that each of its three outcomes points at a different subset of the labelled coins.
The solution
Reveal the full solution
Three weighings suffice, and the scheme below also reveals the direction every time.
Number the coins 1 to 12. Weighing 1: coins 1, 2, 3, 4 against 5, 6, 7, 8.
If it balances, the fake is among 9, 10, 11, 12 and coins 1 to 8 are genuine. Weighing 2: 9, 10, 11 against 1, 2, 3. If that balances, coin 12 is the fake; weigh 12 against 1 to learn its direction. If the left pan is heavy, one of 9, 10, 11 is heavy; weigh 9 against 10, and the heavier pan names the coin, or a balance names 11. If the left pan is light, the same weighing works with "lighter" in place of "heavier".
If the left pan is heavy, then either one of 1, 2, 3, 4 is heavy or one of 5, 6, 7, 8 is light, eight possibilities, and coins 9 to 12 are genuine. Weighing 2: 1, 2, 5 against 3, 6, 9. Three outcomes, each isolating at most three possibilities. Balanced: the fake is among the coins left off, so 4 is heavy or 7 or 8 is light; weigh 7 against 8, and a balance means 4 is heavy, otherwise the lighter pan names the coin. Left heavy again: the cause is 1 or 2 heavy (they stayed on the heavy side) or 6 light (it stayed on the light side); weigh 1 against 2, and a balance means 6 is light. Left light: the tilt reversed, so a coin that switched sides is responsible, which means 3 is heavy or 5 is light; weigh 3 against 9. The case where the right pan is heavy in weighing 1 is the mirror image.
The design rule behind weighing 2 is worth stating plainly: of the eight suspects, keep some on their original side, move some across, and leave some off. The three groups then map one to one onto the three outcomes. A coin that stays on its side keeps the tilt, a coin that crosses reverses it, and a coin that is removed lets the pans balance.
| Coins | Answers | Outcome sequences | Solvable with direction? |
|---|---|---|---|
| 12 | 24 | 27 | Yes |
| 13 | 26 | 27 | No, unless a known-genuine coin is provided |
| 14 | 28 | 27 | No, by counting alone |
The thirteen-coin row is the interesting one, because 26 is less than 27 and counting alone does not rule it out. The obstacle is structural. The first weighing must put k coins on each pan and leave 13 minus 2k off. If it tilts, 2k possibilities remain (k possibly heavy, k possibly light). If it balances, the fake is among the coins left off, in either direction, so 2 times (13 minus 2k) possibilities remain. Two further weighings resolve at most 9. The tilt branch needs 2k at most 9, so k is at most 4. The balance branch needs 26 minus 4k at most 9, so k is at least 4.25. No integer k works. Give the solver one extra coin known to be genuine and the constraint loosens, because that coin can sit on a pan without adding a possibility, and thirteen becomes solvable. Ask only which coin is fake, not its direction, and thirteen is solvable too.
What this puzzle is really testing
Whether you think in outcomes rather than in moves. The balance is a ternary oracle, and three queries cannot separate more than 27 states, however clever the arrangement. Working from the bound downward, each weighing must split the live possibilities into three groups of at most 9, then 3, then 1, and the coin arrangement is forced by that requirement. This is the same discipline as reasoning about logarithms in algorithm analysis: the base of the logarithm is the number of outcomes per query, and the depth is the number of queries you can afford. The eight balls puzzle is the warm-up with a known direction, where 8 states fit inside 9 outcomes with room to spare.
Follow-ups to expect
The general bound: with w weighings and the direction required, at most (3 to the power w minus 3) divided by 2 coins can be handled, which gives 12 for w equal to 3 and 39 for w equal to 4. A sharper follow-up asks for a non-adaptive scheme, where all three weighings are fixed in advance and the answer is read off the outcome triple; such a scheme exists for twelve coins and is a small exercise in error-correcting codes. The sharpest version asks you to prove the bound rather than quote it.