You have 12 coins that look identical. One of them is fake and weighs differently from the real ones, but nobody knows whether it is lighter or heavier. You have a two-pan balance and no weights: it only shows which pan is heavier, or that they balance. What is the smallest number of weighings that guarantees you find the fake coin and say whether it is lighter or heavier?
It looks as if you should halve: 6 against 6, then 3 against 3, which makes 4 or 5 weighings. But a balance has three answers, not two: left pan down, right pan down, or balance. Three weighings give 3³ = 27 outcomes, and there are only 24 cases: 12 coins, each either lighter or heavier. You just have to split the cases into three equal heaps with every weighing.
A classic from puzzle books. No source names a company that asks the 12-coin version, but William Poundstone (2003) lists an easier variant, 8 coins with one lighter, as a Microsoft interview question. This puzzle is loved because the first idea, "split in half", fails here, and the right one makes you think not about coins but about how many answers one instrument can give.
12 coins, numbered 1 to 12. Eleven are genuine and weigh exactly the same. One is fake.
The fake weighs differently, but you do not know whether it is lighter or heavier. You cannot tell it by sight.
A two-pan balance with no weights. You may put any number of coins on each pan. The balance shows one of three things: the left pan is heavier, the right pan is heavier, or they balance.
Name the fake coin and say whether it is lighter or heavier. Not guess it: know it for sure, whichever coin is fake.
What is the smallest number of weighings that guarantees this?
"Split in half: 6 against 6, then 3 against 3, then again… That makes 4 to 6 weighings"
Some weigh the coins in pairs and get up to 7 weighings. In fact 3 are enough, and 2 are not enough with any strategy. The trick is that the first weighing must be 4 against 4, with the other four coins set aside.
12 coins, one fake, lighter or heavier, unknown. Pick the smallest number of weighings that, in your view, guarantees success.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
Splitting in half is the trap: the balance gives three answers, not two. "They balance" is information too, so put it to work.
Count cases, not coins: each coin may be heavier or lighter. How many different histories of results can n weighings produce?
There are 24 cases, and each needs its own sequence of readings. How many sequences do n weighings give? That is only a lower bound: check whether the coins can be arranged to reach it.
Click coins to put them on the left pan, on the right pan, or back off. The pans must hold the same number of coins. The catch: the fake coin has not decided yet which one it is. After each weighing it picks the outcome that leaves you the most work, but it never contradicts earlier results. The grid below shows which of the 24 cases are still possible.
↑ means "this coin is heavier", ↓ means "lighter". Struck-out cases are ruled out.
Pick a strategy. The page runs it on each of the 24 cases (which coin is fake and which way) and counts the weighings exactly. Then it simulates 100,000 random fakes and compares the shares with the exact ones.
The numbers in the grid show how many weighings each case took. A red cell means the strategy could not tell that case from another one.
The key is that a balance answers in three ways, and there are not 12 suspects but 24. Here are five ways to see it.
Finding the coin is not enough: you must also say whether it is lighter or heavier. So each coin gives two cases, "heavy" and "light". That makes 12 · 2 = 24 cases, and any strategy has to tell them all apart.
Every weighing ends in one of three results, so n weighings give at most 3n different histories. Two weighings give 9 histories for 24 cases: some cases must share a history, and you cannot tell them apart. That is the pigeonhole principle. Three weighings give 27 ≥ 24, so 3 weighings might be enough, and round 2 shows that they are.
After the first weighing two remain, so each heap must hold at most 3² = 9 cases. With k coins on each pan, a tilt leaves 2k cases (k coins "heavy" on the lower pan and k "light" on the upper one), and a balance leaves 2 · (12 − 2k). Both numbers are at most 9 only for k = 4.
With 13 coins there are 26 cases, and 26 ≤ 27, so plain counting does not rule out 3 weighings. But the first weighing cannot split 26 as 9 + 8 + 9: a tilt always leaves an even number of cases, so at most 8, and a 4-against-4 balance leaves 10. A full search over all strategies confirms it: 13 coins need 4 weighings. But give yourself one extra coin known to be genuine, and 13 coins fit into 3 weighings.
Coins that have sat on a balanced scale are certainly genuine. You can add them to make a weighing uneven in suspects: three suspects against three references. After a tilt, shuffling the pans helps: 1 and 2 stay on the left, 5 moves to the left, 3 and 6 sit on the right, and 9 is a reference. Every heap after the second weighing holds at most 3 cases, and the third weighing tells 3 cases apart.
An answer out of two equally likely options gives 1 bit; out of three equally likely options it gives 1 trit, which is log₂ 3 ≈ 1.585 bits. Picking one case out of 24 takes log₃ 24 ≈ 2.89 trits, so three weighings suffice only if each one gives almost a full trit. How much the first weighing gives depends on how evenly it splits the cases:
The entropy H = −Σ p · log₃ p reaches its maximum of 1 trit when the three outcomes are equally likely. The split 8 + 8 + 8 gives exactly 1 trit, 3 against 3 gives 0.946, and 6 against 6 only 0.631: a balance is impossible with 6 against 6, so the balance's third answer is wasted.
N coins give 2N cases. The history "every weighing balanced" serves no case: either it cannot happen, or the coin never sat on the scale and you do not know whether it is lighter or heavier.
The first weighing is k against k, with m = N − 2k coins aside. A tilt leaves 2k cases, a balance leaves 2m, and either way n − 1 weighings remain.
The left one holds because 2k is even and 3n−1 is odd. The right one follows from the same "all balanced" argument, now for the remaining weighings.
Add them up: N = 2k + m.
For three weighings: k ≤ 4 and m ≤ 4, so N ≤ 12. The bound is reached: see the classic solution above.
In 1946 Freeman Dyson proved that (3ⁿ − 3)/2 coins can be handled in n weighings, and no more. With one coin known to be genuine, the bound grows to (3ⁿ − 1)/2: 13 coins for three weighings.
The coin puzzle grows in three directions. In mathematics it gives an exact formula and a scheme with every weighing written out in advance. In logic it teaches you to ask questions that split the options evenly. In practice the same rule builds decision trees in machine learning.
Mathematics
The formula (3ⁿ − 3)/2 triples with each weighing: 3, 12, 39, 120 coins. Two changes to the rules add one coin each. With a genuine reference coin, the bound is (3ⁿ − 1)/2. If you only need to find the coin and do not care whether it is lighter or heavier, it is also (3ⁿ − 1)/2: one coin may never touch the scale, and if everything balanced, it is that one.
Both changes together give (3ⁿ + 1)/2, which is 14 coins in 3 weighings. The page checks all these numbers by searching every strategy for 1 to 3 weighings; for 4 weighings (39, 40, 40 and 41) we ran the same search separately. A curiosity: two coins without a reference can never be sorted out, because after 1 : 2 you do not know which one is to blame.
Surprisingly, you do not need to adapt to the results. Dyson showed that every weighing can be written down in advance. Give each coin a three-symbol code: L means "on the left pan", R "on the right", – "aside". A heavy coin then produces a history equal to its code, and a light one produces the mirror image.
For this to work, three conditions are needed: no code is empty, no code is the mirror of another, and every weighing has equal numbers of coins on its pans. There are 26 non-empty codes, forming 13 mirror pairs; you can take only one code from each pair, and one more pair has to go to balance the pans. Which gives 12 again.
Logic
The page will find it in 3 questions, each with three possible answers.
The coin puzzle teaches a general rule: the best question splits the remaining options into parts as equal as possible. Then whatever the answer, it cuts away the most. In Shannon's terms it is the question whose answer has the highest entropy: its result is the hardest to predict, so it tells you the most.
With two answers the rule gives binary search, as in the poisoned wine puzzle. With three answers it gives ternary search: 27 = 3³, so 3 questions. Weighing 6 against 6 is like a question that is never answered "equal": one of the three answers simply goes to waste.
Practice
14 days from Quinlan's classic example: the weather and whether tennis was played that day (tennis comes from later textbooks). Click an attribute to split the days by it.
In 1986 Ross Quinlan described the ID3 algorithm, which builds a decision tree from a table of examples. At every step it chooses the attribute that cuts the uncertainty about the answer the most: the information gain is the entropy before the split minus the average entropy of the parts. It is the same rule as "4 against 4": the best question removes the most uncertainty.
Here the entropy of the answer "played or not" is 0.940 bits. The outlook (sunny, overcast, rain) lowers it the most, by 0.247 bits (Quinlan rounds it to 0.246), so it becomes the root of the tree. After that, humidity decides on sunny days and wind on rainy ones, and the tree classifies all 14 days with no errors. The same rule works in fault diagnosis: you run first the check that splits the possible causes most evenly.
The twelve-coin version first appeared in print in January 1945, as a problem proposed by E. D. Schell in the American Mathematical Monthly. The same year Howard Grossman published a note, "The twelve-coin problem", in Scripta Mathematica.
Freeman Dyson, later famous for his work on quantum electrodynamics, published "The problem of the pennies" in the Mathematical Gazette. He solved the puzzle for any number of weighings and gave a scheme with ternary codes in which every weighing is fixed in advance.
It is a legend, but a good one. Richard Guy and Richard Nowakowski (1995) write that during World War II the puzzle was popular on both sides of the Atlantic, and that it was even suggested to drop it over Germany to sabotage the enemy's war effort. In 1958 Dan Pedoe told the mirror story: enemy agents had supposedly planted it in Britain, since Operational Research spent so many man-hours on it.
In 1612 Claude-Gaspard Bachet de Méziriac showed in his collection "Problèmes plaisans et délectables" that weights of 1, 3, 9 and 27 can weigh any whole amount from 1 to 40 if weights go on both pans. He noted that many had seen this property but nobody had explained it, and proved it. It is the same base 3 with the digits −1, 0, +1.
At Moscow University a team led by Nikolay Brusentsov built Setun, a computer based on balanced ternary: each digit was −1, 0 or +1, like the pans of a balance. About fifty machines were made.
The 14-day weather table appeared in 1986 in Ross Quinlan's paper "Induction of Decision Trees" in the first volume of the journal Machine Learning. In Quinlan the days are just Saturday mornings suitable "for some unspecified activity", and he prints the information gain of the outlook as 0.246 bits. The activity became tennis in later textbooks, and the table is now perhaps the best-known teaching example of decision trees.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.