Weighing and Deduction

A balance scale answers every question with one of three results: the left pan sinks, the right pan sinks, or the pans stay level. After $k$ weighings the full record is a string of $k$ symbols from a three-letter alphabet, so there are at most $3^k$ different records. A procedure can tell two possibilities apart only if they produce different records.

Take 9 balls, one of them heavier. Weigh 3 against 3 and leave 3 off. If the left pan sinks, the heavy ball is one of those three; if the right sinks, one of those; if the pans balance, it is one of the three on the table. Either way 3 suspects remain, and a second weighing of 1 against 1 (third ball off) finishes the job. Two weighings, and $9 = 3^2$.

The same split works at every size. With 27 balls you weigh 9 v 9, then 3 v 3, then 1 v 1: three weighings. With 28 balls you need four, because $28 > 3^3 = 27$. In general, finding one heavier ball among $N$ takes $\lceil \log_3 N \rceil$ weighings.

The usual mistake is to halve. Weighing 4 v 4 on 8 balls puts every ball on the scale, so the level outcome can never happen and that weighing only has two useful results. Halving takes three weighings for 8 balls where splitting 3, 3, 2 takes two.