The Counterfeit Coin, math that surprises you lesson

Nine coins look exactly alike, but one of them is a counterfeit that is heavier than the others, and all the genuine coins weigh the same. A balance scale can compare any two groups of coins, and you may use it only twice. Can you always find the counterfeit? This page builds a two-weighing strategy that works whichever coin is heavy, uses a decision tree to show that one weighing can never be enough, and explains why it matters that the counterfeit is known to be heavier.

Key terms

Counterfeit coin problem

Definition The counterfeit coin problem, in the version on this page, is a puzzle about $n$ coins that look identical. Exactly one coin is counterfeit, all the genuine coins have the same weight, and the counterfeit is known to be heavier than a genuine coin, by an amount nobody is told. The only tool is a balance scale. A weighing places some coins on each of its two pans, and the scale reports one of three results, left pan heavier, right pan heavier, or balance. Each weighing may be chosen after seeing the results of the earlier ones. The task is a strategy that is sure to name the counterfeit within a given number of weighings, whichever coin it is and however much heavier it is. For $n = 9$ two weighings suffice. First weigh coins 1, 2 and 3 against coins 4, 5 and 6. The heavier pan holds the counterfeit, and a balance places it among coins 7, 8 and 9. Then weigh two coins of that group against each other, one on each pan. The heavier coin is the counterfeit, and a balance points to the third coin of the group. One weighing cannot do the job, since it has only three possible results and there are nine possible counterfeits. In general, for $n \ge 1$ coins the fewest weighings that always succeed is the smallest whole number $k$ with $3^k \ge n$ . If the counterfeit might be either heavier or lighter, an unbalanced scale has two explanations, a heavy coin on the pan that went down or a light coin on the pan that went up, so that version is a different puzzle with different answers.

In plain words A balance scale answers with one of three results, so a good weighing splits the suspects into three equal groups, two on the pans and one off the scale, and lets the result point at one group. Nine suspects become three, and three become one.

Example Suppose coin 8 is the counterfeit, although the person weighing does not know it. Coins 1, 2 and 3 against coins 4, 5 and 6 balance, because all six coins on the pans are genuine. The suspects are now coins 7, 8 and 9. With coin 7 on the left pan and coin 8 on the right, the right pan goes down, so coin 8 is the counterfeit, found in two weighings. If coin 2 were the counterfeit instead, the left pan would go down in the first weighing, leaving coins 1, 2 and 3 as suspects, and then coin 1 against coin 2 would send the right pan down and name coin 2. The results differ, but the same rules handle both cases, and they handle the other seven coins in the same way.

Balance scale

Definition A balance scale, or pan balance, has two pans hanging from a beam. It compares the total weight on the left pan with the total weight on the right pan and reports one of three results, left heavier, right heavier, or balance. It does not say how much heavier one side is. In the counterfeit coin problem with one heavier counterfeit, put the same number of coins on each pan. Then the left pan is heavier exactly when the counterfeit is on the left pan, the right pan is heavier exactly when it is on the right pan, and the scale balances exactly when the counterfeit is off the scale. With unequal numbers of coins on the pans, the result can depend on the unknown weight of the counterfeit, so the strategies on this page always use equal numbers.

In plain words Every weighing asks one question with three possible answers. With equal numbers of coins on the pans, the answer simply says where the counterfeit is, on the left, on the right, or off the scale.

Example Weighing coin 1 against coin 2 as the first step splits the nine suspects into groups of sizes $1$ , $1$ and $7$ . A tilt names the counterfeit at once, but a balance leaves seven suspects, and one remaining weighing has only three results for those seven coins. At least two of the seven would produce the same result, so the strategy could not tell them apart. Unequal numbers cause a different problem. Put coin 1 alone against coins 2 and 3 together. If all three are genuine, the side with two coins goes down. If coin 1 is the counterfeit, the result depends on whether it weighs less than, exactly as much as, or more than two genuine coins, and nobody knows which.

Decision tree

Definition A decision tree for a weighing strategy is a branching diagram of every way the weighings can go. It starts at a first weighing, called the root. Each weighing has one branch for each of its three possible results, and each branch leads either to the next weighing, chosen in advance for that case, or to a leaf, where the strategy stops and names a coin. The strategy works when, for every possible counterfeit, following the branches of the actual results ends at a leaf that names that coin. A tree in which every path has at most $k$ weighings has at most $3^k$ leaves. Different counterfeits must end at different leaves, since a leaf names only one coin, so a strategy for $n$ coins that always finishes within $k$ weighings needs $3^k \ge n$ . This count is only a necessary condition. It shows when $k$ weighings are too few, and an actual tree with a working weighing at every branch is still needed to show that $k$ weighings are enough.

In plain words The tree lists every story the weighings can tell. Each weighing at most triples the number of possible stories, and each possible counterfeit needs a story of its own.

Example The nine-coin strategy has the tree below. The first weighing is coins 1, 2 and 3 against coins 4, 5 and 6. Each row gives the second weighing after one first result, and the coin named after each result of the second weighing.

First result	Second weighing	Left heavier	Right heavier	Balance
left heavier	1 against 2	coin 1	coin 2	coin 3
right heavier	4 against 5	coin 4	coin 5	coin 6
balance	7 against 8	coin 7	coin 8	coin 9

The tree has $3 \cdot 3 = 9$ leaves, and each of the nine coins sits at exactly one of them. A single weighing gives a tree with only $3^1 = 3$ leaves, too few for nine coins, so two weighings are the fewest possible.

Ternary search

Definition A ternary search finds one target among $n$ candidates by repeating one step. Split the remaining candidates into three groups, run a test whose three possible results point to the three groups, and keep only the group that the result points to. If each group holds at most a third of the remaining candidates, rounded up to a whole number, then after $k$ tests at most

\left\lceil \frac{n}{3^k} \right\rceil

candidates remain, where $\lceil a \rceil$ means $a$ rounded up to a whole number. So the target is found within $k$ tests as soon as $3^k \ge n$ , which matches the bound from the decision tree. In the counterfeit coin problem the three groups are the coins on the left pan, the coins on the right pan and the coins off the scale, and the two groups on the pans hold the same number of coins. In computer science the same name is also used for related methods that split a sorted list or an interval into thirds.

In plain words A test with three results makes the most progress, whatever happens, when each of its results leaves the same number of suspects. Splitting the suspects into thirds means that whatever the scale shows, about two thirds of them are cleared.

Example With $27$ coins, weigh $9$ against $9$ and leave $9$ off the scale. Whatever the result, $9$ suspects remain. Weighing $3$ of them against $3$ others leaves $3$ , and weighing $1$ against $1$ names the coin, so three weighings suffice. Since $3^2 = 9 < 27$ , no strategy can always succeed with two. A strategy that used only yes-or-no tests would need five of them for $27$ candidates, because

2^4 = 16 < 27 \le 32 = 2^5.

Check yourself

There are eight coins, one of them heavier, and two weighings. A friend starts by weighing four coins against four. Explain why that can fail, and give a strategy that always works.

Show the answer

All eight coins are on the scale, so the first weighing can never balance, and one of its three results is wasted. The heavier pan leaves four suspects, and the one remaining weighing has only three results, so at least two of the four suspects would produce the same result and could not be told apart.

Instead, weigh coins 1, 2 and 3 against coins 4, 5 and 6, leaving coins 7 and 8 off the scale. If a pan goes down, weigh two coins from that pan against each other, as in the nine-coin strategy. If the pans balance, weigh coin 7 against coin 8, and the heavier one is the counterfeit. This last weighing cannot balance, since one of the two coins is the counterfeit. The groups of sizes $3$ , $3$ and $2$ are not all equal, but each holds at most three coins, which is all that the second weighing needs.

How many weighings are needed to find one heavier coin among $100$ coins? Describe a strategy that achieves that number.

Show the answer

Four weighings are not enough, and five are, because

\begin{gathered} 3^4 = 81 < 100, \\[0.4em] 3^5 = 243 \ge 100. \end{gathered}

A tree of four weighings has at most $81$ leaves, fewer than the $100$ possible counterfeits. For five weighings, weigh $33$ coins against $33$ and leave $34$ off the scale, so at most $34$ suspects remain. Weigh $12$ of them against $12$ others, leaving $10$ aside, so at most $12$ remain. Then $4$ against $4$ with $4$ aside leaves at most $4$ , one against one with two aside leaves at most $2$ , and a last weighing of one against one names the coin. In the worst case the number of suspects goes $100$ , $34$ , $12$ , $4$ , $2$ , $1$ , which takes five weighings.

Change a rule. Both weighings must be planned before either one is made, so the second weighing can no longer depend on the first result. Can the counterfeit among nine coins still always be found with two weighings?

Show the answer

Yes. Let weighing A be coins 1, 2 and 3 against coins 4, 5 and 6, and let weighing B be coins 1, 4 and 7 against coins 2, 5 and 8. Each weighing has three coins on each pan. Weighing A tells which group of three holds the counterfeit, and weighing B tells its position in the group, since the first coin of every group is on the left pan of B, the second is on the right pan, and the third is off the scale.

Result of A	B left heavier	B right heavier	B balances
left heavier	coin 1	coin 2	coin 3
right heavier	coin 4	coin 5	coin 6
balance	coin 7	coin 8	coin 9

Each of the nine pairs of results belongs to exactly one coin, so the pair names the counterfeit. Each coin’s two results work like a two-digit address in which every digit has three possible values.