Counterfeit Coins: Heavier

Among a collection of 9 coins, one is distinctly heavier than the rest. Using a traditional two-pan balance only twice, how would you identify this heavier coin?

Answer

Label the coins $C_1, C_2, \dots, C_9$ . First, weigh 3 coins against 3 other coins, for instance $$C_1, C_2, C_3$$ vs. $$C_4, C_5, C_6$$ .

If one side is heavier (assume $$C_1, C_2, C_3$$ is heavier), then weigh $$C_1$$ vs. $$C_2$$ .
- If they balance, $$C_3$$ is the heavier coin.
- Otherwise, the heavier side identifies the counterfeit (heavier) coin.
If the scale balances, the heavier coin is among the remaining three ( $$C_7, C_8, C_9$$ ). Weigh $$C_7$$ vs. $$C_8$$ .
- If one side is heavier, that is the counterfeit coin.
- Otherwise, $$C_9$$ is the heavier coin.

Notes and comments

Comment 1: In general, if you have $$x$$ coins and need to find one heavier coin among them, the key fact is:

3^{k-1} < x \;\le\; 3^k \quad \Longrightarrow \quad \text{you need exactly } k \text{ weighings}.

Equivalently, $k = \lceil \log_3(x) \rceil$ . This holds for all numbers $$x$$ .

For example for numbers $$x$$ not equal to $$3^k$$ , you divide the coins into three groups as equally as possible. The idea for this is so that the remaining pile (after "round one"), whichever it is, can be done in only $$k-1$$ weighings which with the initial scale of the piles gives us a total of $$k$$ weighings. For example, if $$x = 26$$ , we split them into piles of $$9$$ , $$9$$ , and $$8$$ .