Nine Balls, Two Weighings, Heavier Direction Known

Brain Teaser · Medium · Free problem

You have 9 identical-looking balls. One is counterfeit and heavier than the rest (you know the direction). You have a balance scale and may use it exactly 2 times.

  1. Give a deterministic strategy that always identifies the counterfeit ball in at most 2 weighings.
  1. Prove that 2 weighings are both sufficient and necessary (i.e., 1 weighing is not enough).

Hints

  1. Each balance-scale weighing has exactly 3 outcomes. How many distinct outcome sequences do 2 weighings give you?
  2. Since $3^2 = 9$ and you have 9 balls, you need each weighing to be maximally informative -- split the suspects into 3 equal groups each time.
  3. For the necessity proof, argue by pigeonhole: 1 weighing has only 3 outcomes, which cannot distinguish 9 possibilities.

Worked Solution

How to Think About It: Each weighing of a balance scale has 3 possible outcomes: left heavy, right heavy, or balanced. So 2 weighings give $3^2 = 9$ distinct outcome sequences -- exactly the number of balls. This is a strong hint that 2 weighings should be both sufficient and necessary: we need to distinguish 9 possibilities, and we have exactly 9 information outcomes. The strategy is to divide the balls into 3 equal groups at each step, since base-3 is the natural decomposition for a balance scale.

Key Insight: Divide into thirds. A balance scale with known direction (heavier) gives a ternary search: the heavy ball is in the heavier group, or if balanced, it is in the group not weighed.

The Method:

Weighing 1: Divide the 9 balls into three groups of 3: $\{1,2,3\}$, $\{4,5,6\}$, $\{7,8,9\}$. Place $\{1,2,3\}$ on the left and $\{4,5,6\}$ on the right.

  • If left side is heavier: the counterfeit is in $\{1,2,3\}$.
  • If right side is heavier: the counterfeit is in $\{4,5,6\}$.
  • If balanced: the counterfeit is in $\{7,8,9\}$.

Weighing 2: Take the suspect group of 3. Place one ball on the left and one on the right; leave the third aside.

For example, if the suspect group is $\{1,2,3\}$: place ball 1 on the left and ball 2 on the right.

  • If left side is heavier: ball 1 is counterfeit.
  • If right side is heavier: ball 2 is counterfeit.
  • If balanced: ball 3 is counterfeit.

This always identifies the counterfeit in exactly 2 weighings.

Proof of sufficiency and necessity:

*Sufficiency:* The strategy above works for all 9 cases. Each of the $3^2 = 9$ outcome pairs (LL, LR, LB, RL, RR, RB, BL, BR, BB, where L = left heavy, R = right heavy, B = balanced) maps to a unique ball. This is a bijection, so the strategy is correct and uses 2 weighings.

*Necessity (1 weighing is not enough):* With 1 weighing, there are at most 3 possible outcomes. But there are 9 balls to distinguish. Since $3 < 9$, by the pigeonhole principle, at least two balls must produce the same outcome, and they cannot be distinguished. Therefore 1 weighing is insufficient.

More precisely: in a single weighing, you place some balls on each side. The outcome "left heavy" identifies the counterfeit as being in the left group, "right heavy" in the right group, and "balanced" means it was not weighed. To identify one ball uniquely from each outcome, each group can have at most 1 ball, so you can distinguish at most 3 balls in one weighing. Since $9 > 3$, one weighing is not enough.

Answer: Divide into groups of 3. Weighing 1 identifies which group; weighing 2 identifies which ball within the group. Two weighings are necessary and sufficient because $3^1 = 3 < 9 \leq 3^2 = 9$.

Intuition

Balance-scale puzzles are really about information theory in base 3. Each weighing produces one of 3 outcomes (left, right, balanced), so $k$ weighings produce $3^k$ distinguishable outcome sequences. To identify one defective item among $n$, you need $3^k \geq n$, or $k \geq \lceil \log_3 n \rceil$. For 9 balls with known direction, $\lceil \log_3 9 \rceil = 2$, and the strategy achieves this bound.

The problem becomes harder when the direction is unknown (heavier or lighter). Then each ball has 2 possible states (heavy or light), giving

n$ possibilities, and you need $3^k \geq 2n$. For 12 balls with unknown direction, this gives $k \geq 3$ (since $3^3 = 27 \geq 24$), which is the classic 12-ball puzzle. The information-theoretic lower bound is tight in all these cases, which is a beautiful fact about ternary coding.

Open the full interactive solver →