Finding a Heavier Coin

Lower bound. Each weighing has three outcomes: left heavier, right heavier, or balance. A strategy of at most $k$ weighings may let later weighings depend on earlier results, but it can still be drawn as a ternary decision tree of depth $k$. Such a tree has at most $3^k$ leaves.

Each of the $18$ beans could be the heavy one, and each possibility must end at a different leaf. So we need $3^k \ge 18$. Since $3^2 = 9 < 18$, two weighings cannot suffice.

Three weighings suffice.

• First weighing: split the beans into three groups of $6$ and weigh two of the groups against each other. If one pan is heavier, the heavy bean is in that group. If the pans balance, it is in the third group. Either way, $6$ candidates remain.
• Second weighing: split these $6$ into three pairs and weigh two pairs against each other. By the same reasoning, $2$ candidates remain.
• Third weighing: put one remaining bean on each pan. The heavier bean is the odd one.

Generalisation. The same argument works for $n$ beans with one known to be heavier. The counting bound gives $3^k \ge n$. Conversely, a weighing can always split the candidates into two equal pans and a remainder, each part of size at most $\lceil m/3\rceil$, where $m$ is the current number of candidates. Hence the minimum number of weighings is $\lceil \log_3 n\rceil$.