Counterfeit Coin With One Weighing
You have 9 visually identical coins. Exactly one of them is counterfeit -- it is either heavier or lighter than the genuine coins, but you don't know which.
You have a balance scale and you may use it exactly once.
Is it possible to *always* identify which coin is counterfeit and determine whether it is heavier or lighter?
Give a rigorous information-theoretic argument. Specifically, count the number of distinguishable hypotheses and compare it to the number of possible outcomes of a single weighing.
Hints
- Count the total number of possible states of the world -- how many (coin, direction) pairs are there?
- A balance scale has exactly three possible outcomes per weighing. Compare this to your hypothesis count.
- Apply the pigeonhole principle: can you map $18$ hypotheses injectively into $3$ outcomes?
Worked Solution
How to Think About It: Before touching any coins, ask yourself: how much information do I need, and how much can I get? This is the right reflex for any "can you do X in $k$ weighings?" problem. A balance scale has three outcomes per weighing (left heavy, right heavy, balanced), so one weighing gives you at most $\log_2 3 \approx 1.58$ bits -- equivalently, it can distinguish among at most 3 hypotheses. Now count how many hypotheses you actually need to separate.
Quick Estimate: There are 9 coins, and for each coin there are 2 possibilities (it's heavier or lighter). That gives $9 \times 2 = 18$ hypotheses total. One weighing has 3 outcomes. Since $18 > 3$, you cannot map 18 hypotheses injectively to 3 outcomes. Done -- it's impossible.
Approach: We formalize this as a pigeonhole / information-theoretic argument.
Formal Solution:
Label the coins $c_1, c_2, \ldots, c_9$. The unknown state of the world is a pair $(i, d)$ where $i \in \{1, 2, \ldots, 9\}$ identifies the counterfeit coin and $d \in \{H, L\}$ indicates whether it is heavier or lighter. The total number of hypotheses is:
$$|\mathcal{H}| = 9 \times 2 = 18$$
A single weighing places some subset $A$ of coins on the left pan and some subset $B$ on the right pan (with $|A| = |B|$ and $A \cap B = \emptyset$). The outcome is one of three values:
$$\mathcal{O} = \{\text{left heavy},\ \text{balanced},\ \text{right heavy}\}$$
So $|\mathcal{O}| = 3$.
To "always identify the counterfeit coin and its direction" means that for every possible hypothesis $(i, d) \in \mathcal{H}$, the observed outcome must uniquely determine $(i, d)$. Formally, this requires an injective function $f : \mathcal{H} \to \mathcal{O}$.
But an injective function from an 18-element set to a 3-element set cannot exist, since $18 > 3$. By the pigeonhole principle, at least $\lceil 18/3 \rceil = 6$ hypotheses must map to the same outcome. Among those 6 hypotheses sharing one outcome, we have no way to distinguish them.
Therefore, no strategy using a single weighing can always determine both the identity and direction of the counterfeit coin among 9 coins.
Remark -- what CAN one weighing solve? The information-theoretic bound says one weighing can handle at most 3 hypotheses. If you only had 1 coin that might be heavy or light plus one known-good reference coin, that's $1 \times 2 = 2$ hypotheses -- solvable. For the classic problem where you know the counterfeit is *heavier* (eliminating the $d$ unknown), 9 coins give 9 hypotheses, and you would need $\lceil \log_3 9 \rceil = 2$ weighings. So even with that simplification, one weighing is not enough for 9 coins (though it works for 3).
Answer: No. There are 18 hypotheses (9 coins $\times$ 2 directions) but only 3 distinguishable outcomes from one weighing. By the pigeonhole principle, no single weighing can always identify the counterfeit coin and its direction.
Intuition
This is a pure information-theoretic bottleneck argument, and it shows up constantly in puzzle-style interviews and in real system design. The idea is simple: before you think about clever strategies, count how much information you need versus how much your measurement can provide. A balance scale is a ternary measurement device -- each use gives you $\log_2 3$ bits. If you need to distinguish among $N$ hypotheses, you need at least $\lceil \log_3 N \rceil$ weighings. For 9 coins with unknown direction, $N = 18$, so you need at least $\lceil \log_3 18 \rceil = 3$ weighings. (In fact, the classic 12-coin puzzle shows that 3 weighings can handle up to $3^3 = 27$ hypotheses, which is enough for 12 coins with unknown direction plus one extra outcome.)
The broader lesson: whenever someone asks "can you do X with $k$ measurements?", start by counting hypotheses and comparing to the measurement capacity. This kills impossible problems instantly and sets a lower bound on the number of measurements for feasible ones. In quant work, the same logic appears in experimental design, optimal question-asking (like binary search vs. ternary search), and channel capacity arguments.