Finding the heavy coin with a balance

1. Strategy. Induction on $k$. For $k=0$ there is a single coin. For $k\ge1$, divide the $3^k$ coins into three groups $A,B,C$ of $3^{k-1}$ coins and weigh $A$ against $B$.
- If $A$ is heavier, the heavy coin is in $A$; if $B$ is heavier, it is in $B$.
- If the scale balances, it is in $C$.

In each case, the heavy coin is among $3^{k-1}$ coins, which can be found in $k-1$ further weighings by the induction hypothesis. In total $k$ weighings suffice.

2. Lower bound. Fix a strategy using at most $k$ weighings. Each possible heavy coin gives a sequence of at most $k$ outcomes, each outcome being one of $3$ values. There are at most $3^k$ such sequences.

If two different coins gave the same sequence, the strategy could not tell them apart. So a strategy that always finds the coin must give distinct sequences to distinct coins, hence $N\le3^k$. Therefore $N>3^k$ coins cannot be handled in $k$ weighings.

Remark. An information-theoretic argument: each weighing provides at most $\log_23$ bits of information. The harder variant with a coin that may be heavier or lighter is solved by the same principle: $12$ coins in $3$ weighings.

Lesson. Optimal algorithm problems come in two halves: an explicit strategy, and a counting argument on outcomes showing that nothing better is possible.