You have 9 visually identical balls. Exactly one ball has a slightly higher weight, the other eight all weigh the same. You have a balance scale that can compare the total weight of objects on the left and right pans. How many weighings are necessary and sufficient to identify the heavier ball?
Each weighing has three possible outcomes: left heavy, right heavy, or balance.
Suppose we put 3 balls on both sides of the scale; if the scale tips, we know that the heavier ball is in the tipped side. If the scale remains balanced, we know that the heavier ball is among the 3 balls that were left out. This allows us to focus on a set of just 3 balls.
Continue by placing 1 ball from those 3 on each side of the scale. If the scale tips, we know which side contains the heavier ball; if it remains balanced, the last remaining ball is the heavier one. Thus we identify the heavier ball in two more weighings after the initial 3-vs-3 split.
Two weighings are needed
What if we have N balls?
Same counting idea: each weighing gives three outcomes, so with k weighings you can distinguish up to 3k outcome sequences. Use this to bound the number of balls you can handle.
With each measurement we obtain three possible outcomes, so each weighing increases the amount of information threefold. Therefore each weighing reduces the size of the candidate set by about a factor of three, and to cover N balls we need the smallest integer k with 3k ≥ N. Equivalently:
$$k = \left\lceil \log_3 N \right\rceil$$
Here \(\lceil x \rceil\) denotes the ceiling (rounding up to the nearest integer).
In practice, construct the weighings by repeatedly splitting the candidate set into three (as evenly as possible) and comparing two groups; each weighing reduces the candidate set by about a factor of three.
What if we only know the special ball is different (unknown heavier or lighter)?
Here the odd ball may be heavier or lighter, so for N balls there are 2N possibilities (which ball × heavier/lighter).
The classic approach is to design three weighings so that each (ball, direction) pair produces a unique outcome sequence — this is the same coding idea used in the 12-ball puzzle. For N=9 this requires k with 3k ≥ 18, so k=3 weighings suffice. Concretely, choose assignments of balls to left/right/absent in each weighing so the pattern of left/right/balance identifies both which ball and whether it is heavier or lighter.
