Maximum Coins Identifiable With Three Weighings

Brain Teaser · Medium · Free problem

You have a balance scale and are allowed exactly 3 weighings. Among $n$ coins, exactly one is counterfeit and you know it is heavier than the genuine coins.

What is the maximum number $n$ of coins for which you can always identify the counterfeit coin in 3 weighings?

  1. Derive an information-theoretic upper bound on $n$.
  2. Give a constructive weighing strategy that achieves this bound.

Hints

  1. Think about how much information a single weighing gives you. How many distinguishable outcomes does a balance scale produce?
  2. With $k$ weighings, you can distinguish among $3^k$ outcome sequences. How does this bound the number of coins?
  3. Divide the candidate coins into three equal groups and weigh two of them. The outcome always eliminates two-thirds of the candidates.

Worked Solution

How to Think About It: Each weighing of a balance scale has three possible outcomes: left side heavier, balanced, or right side heavier. Three weighings give $3^3 = 27$ distinct outcome sequences. Since we need each possible counterfeit coin to map to a unique outcome sequence, we can handle at most 27 coins. The key question is whether 27 is actually achievable -- i.e., can we design a strategy where every coin produces a distinct triple of outcomes? Because we know the direction of the defect (heavier), a simple "divide into thirds" strategy works perfectly.

Quick Estimate: Each weighing is a ternary digit of information. Three weighings give $3^3 = 27$ distinguishable states. So the answer should be $n = 27$. A quick sanity check: with 2 weighings we could handle $3^2 = 9$ coins (the classic puzzle), so 27 for 3 weighings follows the same pattern.

Approach: We prove the upper bound via an information-theoretic argument, then show a constructive strategy (successive trisection) that matches it.

Formal Solution:

*Part 1: Information-Theoretic Upper Bound*

Each weighing produces one of 3 outcomes: left heavy ($L$), balanced ($B$), or right heavy ($R$). Three weighings produce an outcome string in $\{L, B, R\}^3$, giving $3^3 = 27$ distinct outcomes. Each coin must map to at least one unique outcome string (otherwise two coins with the same outcome string could not be distinguished). Therefore:

$n \leq 3^3 = 27$

*Part 2: Constructive Strategy*

Label the 27 coins

, 2, \ldots, 27$. The strategy uses successive trisection -- at each step, divide the remaining candidates into three equal groups and weigh two of them against each other.

Weighing 1: Divide all 27 coins into three groups of 9: - Group $A$: coins 1--9 - Group $B$: coins 10--18 - Group $C$: coins 19--27

Weigh $A$ vs. $B$: - If $A$ is heavier: the counterfeit is in $A$ (coins 1--9) - If $B$ is heavier: the counterfeit is in $B$ (coins 10--18) - If balanced: the counterfeit is in $C$ (coins 19--27)

In every case, 9 candidates remain.

Weighing 2: Take the 9 remaining candidates and divide into three groups of 3. Weigh one group against another: - Heavier side contains the counterfeit - If balanced, the counterfeit is in the unweighed group

3 candidates remain.

Weighing 3: Take the 3 remaining candidates. Weigh one against another: - Heavier coin is the counterfeit - If balanced, the unweighed coin is the counterfeit

1 candidate remains -- the counterfeit is identified.

Each weighing reduces the candidate set by a factor of 3. Starting from 27, we get

7 \to 9 \to 3 \to 1$, exactly pinpointing the counterfeit.

*Generalizing:* With $k$ weighings, the maximum number of coins is $n = 3^k$. The strategy extends naturally: each weighing trisects the candidate pool.

Answer: The maximum is $n = 27$ coins. The information-theoretic bound is $n \leq 3^3 = 27$ (since each of 3 weighings yields 3 outcomes), and this is achieved by the trisection strategy: divide candidates into three equal groups, weigh two groups, and the outcome tells you which third contains the counterfeit. Three rounds of trisection reduce 7 \to 9 \to 3 \to 1$.

Intuition

This problem is really about information theory dressed up in a puzzle. A balance scale is a physical ternary oracle -- each use gives you exactly $\log_2 3 \approx 1.585$ bits of information. With 3 weighings you get about 4.75 bits total, which can distinguish among ^{4.75} \approx 27$ possibilities. The reason the bound is tight is that knowing the direction of the defect (heavier) lets you fully exploit all three outcomes of each weighing. Each outcome directly tells you which third of the candidates contains the counterfeit, so no information is wasted.

This changes dramatically in the harder variant where you don't know whether the counterfeit is heavier or lighter. There, some outcome sequences must be "spent" distinguishing direction as well as identity. With $n$ coins and unknown direction, there are n$ hypotheses (each coin could be heavy or light), so 3 weighings can handle at most $\lfloor(3^3 - 3)/2\rfloor = 12$ coins. The factor-of-two-plus reduction from 27 to 12 is a vivid demonstration of how side information (knowing the defect direction) dramatically increases the power of a measurement procedure -- a principle that shows up everywhere from experimental design to trading, where knowing the direction of a signal lets you extract far more from limited observations.

Open the full interactive solver →