Twelve Balls and a Balance Scale

Brain Teaser · Hard · Free problem

You have 12 balls that look identical. One of them is the odd ball -- it is either heavier or lighter than the rest, but you do not know which. You have a two-pan balance scale.

  1. Design a strategy that guarantees you can identify the odd ball AND determine whether it is heavier or lighter, using the minimum number of weighings.
  1. Prove that your strategy is optimal by establishing an information-theoretic lower bound on the number of weighings required.

Hints

  1. Count the total number of possible outcomes (which ball is odd, and is it heavier or lighter?) and think about how much information each weighing provides.
  2. Each weighing has 3 possible results, so $k$ weighings can distinguish at most $3^k$ cases. Use this to establish a lower bound.
  3. For the first weighing, put 4 balls on each side and leave 4 off. In each subsequent weighing, mix balls from different groups and include known-normal balls as references.

Worked Solution

How to Think About It: There are 12 balls and the odd one could be any of them, and it could be heavier or lighter. That is

2 \times 2 = 24$ possible outcomes you need to distinguish. Each weighing has three possible results (left side heavier, right side heavier, balanced), so each weighing gives you at most $\log_2 3 \approx 1.585$ bits of information. With $k$ weighings you can distinguish at most $3^k$ outcomes. Since $3^2 = 9 < 24 \leq 27 = 3^3$, you need at least 3 weighings. The challenge is constructing a strategy that actually achieves this bound.

Quick Estimate: Lower bound: $3^k \geq 24$ requires $k \geq 3$. So 3 weighings is the minimum if achievable. We will show a concrete strategy that works in exactly 3 weighings.

Approach: We design a decision tree with 3 weighings, each branching into 3 outcomes, covering all 24 possibilities.

Formal Solution:

Label the balls

$ through
2$.

*Weighing 1: Place balls $\{1, 2, 3, 4\}$ on the left and $\{5, 6, 7, 8\}$ on the right. Balls $\{9, 10, 11, 12\}$ are off the scale.*

Case A: Scale balances. The odd ball is among $\{9, 10, 11, 12\}$, and balls

$-$8$ are all normal.

  • *Weighing 2:* Put $\{9, 10, 11\}$ on the left, $\{1, 2, 3\}$ (known normal) on the right.
  • *Balances:* Ball
    2$ is odd. Weighing 3: weigh
    2$ vs
    $. If
    2$ is heavier, it is the heavy odd ball; if lighter, it is the light odd ball.
  • *Left heavy:* Odd ball is among $\{9, 10, 11\}$ and is heavy. Weighing 3: weigh $9$ vs
    0$. If one is heavier, that is the odd ball (heavy). If balanced,
    1$ is the odd ball (heavy).
  • *Left light:* Odd ball is among $\{9, 10, 11\}$ and is light. Weighing 3: weigh $9$ vs
    0$. If one is lighter, that is the odd ball (light). If balanced,
    1$ is the odd ball (light).

Case B: Left side heavy (balls $\{1,2,3,4\}$ heavier than $\{5,6,7,8\}$). The odd ball is among these 8, and balls $9$-

2$ are normal. Either one of $\{1,2,3,4\}$ is heavy or one of $\{5,6,7,8\}$ is light.

  • *Weighing 2:* Put $\{1, 2, 5\}$ on the left, $\{3, 6, 9\}$ on the right. (Ball $9$ is known normal.)
  • *Balances:* The odd ball is $4$ (heavy), $7$ (light), or $8$ (light). Weighing 3: weigh $7$ vs $8$. If $7$ is lighter, $7$ is odd (light). If $8$ is lighter, $8$ is odd (light). If balanced, $4$ is odd (heavy).
  • *Left heavy:* Either
    $ or
$ is heavy, or $6$ is light. Weighing 3: weigh
$ vs
$. If one is heavier, it is the odd ball (heavy). If balanced, $6$ is odd (light).
  • *Left light:* Either $3$ is heavy or $5$ is light. Weighing 3: weigh $3$ vs $9$ (normal). If $3$ is heavier, $3$ is odd (heavy). If balanced, $5$ is odd (light).

    • Case C: Left side light. By symmetry with Case B (swap the roles of "heavy" and "light" and swap the left/right groups), the same logic applies with all heavy/light labels reversed.

    *Optimality Proof:*

    There are 24 possible outcomes (12 choices for the odd ball $\times$ 2 for heavier/lighter). Each weighing produces one of 3 results. A strategy using $k$ weighings corresponds to a ternary decision tree with at most $3^k$ leaves. To distinguish all 24 outcomes, we need $3^k \geq 24$, which requires $k \geq 3$. Since we exhibited a strategy achieving $k = 3$, the minimum number of weighings is exactly $3$.

    Answer: The minimum number of weighings is $3$. The information-theoretic lower bound ($3^3 = 27 \geq 24$) shows 2 weighings are insufficient, and the strategy above achieves identification in exactly 3 weighings.

    Intuition

    This is the classic information-theoretic puzzle. The core principle is that a balance scale is a ternary oracle -- each weighing partitions the remaining possibilities into three groups. To use 3 weighings optimally, each weighing must split the remaining possibilities as evenly as possible into thirds. With 24 possibilities and $3^3 = 27$ leaves, there is just enough room, but no slack -- you cannot waste a single outcome on a redundant branch.

    The deeper lesson is about information-theoretic lower bounds. In any search or classification problem, if each query gives you $b$ possible answers and you have $N$ cases to distinguish, you need at least $\lceil \log_b N \rceil$ queries. This principle applies well beyond puzzles: it underlies binary search, comparison-based sorting lower bounds ($\lceil \log_2 n! \rceil$ comparisons), and entropy arguments in coding theory. The hard part is usually constructing a strategy that achieves the bound, not proving the bound itself.

    Open the full interactive solver →