Ninety coins, one fake, and the weighing that fits by one

Ninety coins, one of them counterfeit. It does not weigh what the others weigh, nobody says by how much, and nobody says whether it is heavier or lighter. You have a two-pan balance that never reads a weight and only ever reports which side fell. Each weighing costs a hundred dollars. Name the coin, name the direction, and spend as little as you can guarantee.

The answer is five weighings and five hundred dollars. Getting there needs two arguments of completely different kinds, and the interesting thing about this problem is that neither one can do the other’s job. Counting rules out four, and it rules it out against every strategy that could ever be written. But counting will not hand you a method, and no amount of it proves that five are enough. That half is settled only by building something.

Two miscounts, one line into the problem

The instinct is to halve. Forty-five against forty-five, discard the side that cannot hold the fake, repeat: seven steps, seven hundred dollars. It fails immediately, and it fails on the sentence people skim past. You do not know which way the fake is off. If the left pan falls, the counterfeit is either on the left being heavy or on the right being light. The tilt names neither the pile to keep nor the pile to discard.

So the unknown is not one of ninety things. It is a pair, and there are a hundred and eighty of them. The second miscount is quieter: a balance answers three ways, not two, and the third answer is the one that ends up carrying the solution.

What four weighings can and cannot say

Fix any strategy that always finishes within $n$ weighings. Which weighing it performs next depends only on what it has seen so far, so the whole thing is a decision tree of depth $n$ in which every node has three children. Play a world through it and it produces one outcome history. Two worlds that produce the same history arrive at the same leaf and are handed the same answer, so if the strategy is correct they must have been the same world.

This is airtight for adaptive strategies, which is worth saying because the argument looks like it should only cover fixed ones. Adaptivity changes which weighing sits at a node; it cannot change the fact that a node has three children.

One honest caveat, since the “a hundred and eighty, not ninety” framing is rhetorically the most satisfying part of the setup: it is not what forces five weighings here. Ninety on its own already exceeds eighty-one. A candidate let off the direction still needs five. The pair matters enormously for the capacity law further down, and for why halving fails, but the bound at ninety does not lean on it.

Building the five

The counting says something sharper than a number if you read it as a design constraint. A weighing that can only ever tilt has thrown one of its three answers away, and a strategy made of those has $2^{4} = 16$ histories rather than eighty-one. Coins therefore have to be left off the scale on purpose.

Weigh forty against forty and leave ten on the table. If it tilts, every coin on the heavy side is a coin that could be heavy, every coin on the light side could be light, and the ten that never went on are innocent, because the fake was on the scale. Eighty possibilities survive, against a ceiling of eighty-one for the four weighings that remain.

Forty a side is the largest opening the budget admits, though not the only workable one: every equal split from twenty-five to forty a side gets there. From the tilt branch the recursion has something it did not have at the start, namely coins known to be genuine. Those are not spare parts. They let you level a pair of unequal piles, and they let you put maybe-heavy coins against maybe-light ones, which is what makes a single tilt cut the field into thirds rather than halves: eighty, twenty-seven, nine, three, one.

The capacity, and a four-line proof

With no coin known genuine at the start, and the direction required, $n$ weighings settle at most

The value at $n = 3$is twelve, which is the classical twelve-coin puzzle, sitting inside the general law as one case. The result is published: Halbeisen and Hungerbühler prove both directions of it in 1995. But it also has a short proof, and the proof explains the stray $-3$ that otherwise looks arbitrary.

So the missing three outcomes are three branches each forced to waste one, by parity. It is worth being careful about what that costs and why, because the natural gloss — that all three are the price of having no reference coin — is wrong. Exactly one of them is a pure parity loss that you pay even holding a genuine coin, which is why the reference-coin capacity is $(3^{n}-1)/2$ rather than $(3^{n}+1)/2$. Only the other two are the price of starting cold.

Which formula belongs to which problem

Nearly all the confusion around this problem comes from four rule sets being quoted with each other’s answers. Two conditions decide it: whether a coin known to be genuine is available, and whether the direction has to be reported.

Three traps live in that table. There is no third formula: $(3^{n}-3)/2 + 1$ is identically $(3^{n}-1)/2$, so quoting it as a separate rule set is a self-inflicted error. Whether you are told a counterfeit exists changes nothing in the left-hand column and only matters in the right-hand one. And the widely repeated bound $(3^{n}-1)/2$ from the standard information-theory textbook treatment is an upper bound, not a capacity: it permits thirteen coins in three weighings, where the true answer is twelve.

Worst case is not average case

The word doing the most work in the question is guarantee. Minimising the worst cost and minimising the expected cost can be different problems: a strategy judged on the average may leave one branch expensive because it is rare, while a worst-case strategy has to fit every branch inside the budget.

It is worth resisting the temptation to oversell that, because for this instance the gap is small. Expected cost needs a prior to even be defined; take the uniform one, and the shortest possible average over 180 leaves of a ternary tree is

attained with thirty-one leaves at depth four and a hundred and forty-nine at depth five. So the whole prize for optimising the average here is about seventeen dollars. The distinction is real and it is the thing being tested; the arithmetic just happens to be gentle about it in this particular case.

Sources and further reading

• L. Halbeisen and N. Hungerbühler, “The general counterfeit coin problem”, Discrete Mathematics 147 (1995) 139–150. Theorems 1 and 2 at $b = 1$ give both directions of $(3^{n}-3)/2$.
• C. A. B. Smith, “The counterfeit coin problem”, Mathematical Gazette31 (1947) 31–39.
• F. J. Dyson, “The problem of the pennies”, Mathematical Gazette30, no. 291 (1946) 231–234. Frequently miscited as “the pesetas”; the 1931 in the usual citation is a note number, not a year.
• Balance puzzle — correct, but its summary table omits this exact variant and changes two conditions at once between rows, which reliably produces the inference that the answer at $n = 3$ is thirteen.
• Decision tree model
• Information content