Finding the Heavy Bean With a Balance Scale
You have 18 beans. 17 of them are identical, and one is slightly heavier than the rest. You also have a balance scale (no weights -- just two pans).
What is the minimum number of weighings needed to guarantee you identify the heavier bean?
Hints
- Think about how much information each weighing gives you -- a balance scale has three possible outcomes, not two.
- If you have $n$ candidates and each weighing has 3 outcomes, you need at least $\lceil \log_3 n \rceil$ weighings. What does that give for $n = 18$?
- Split the beans into three equal groups and weigh two of them against each other. The group containing the heavy bean is identified by which side tips (or by the fact that they balance). Repeat.
Worked Solution
How to Think About It: This is a classic information-theory puzzle disguised as a physical problem. A balance scale has three possible outcomes per weighing: left side heavier, right side heavier, or balanced. Each weighing gives you one "trit" (base-3 digit) of information. The question becomes: how many trits do you need to pinpoint one bean out of 18?
Quick Estimate: With $k$ weighings, you can distinguish among at most $3^k$ outcomes. We need $3^k \geq 18$. Since $3^2 = 9 < 18$ and $3^3 = 27 \geq 18$, the information-theoretic lower bound is 3 weighings. Two weighings cannot possibly suffice. But we still need to show 3 weighings actually work by constructing a strategy.
Approach: Divide-and-conquer in base 3. At each step, split the remaining candidates into three equal (or near-equal) groups.
Formal Solution:
1. Weighing 1: Split the 18 beans into three groups of 6. Place Group A (6 beans) on the left pan and Group B (6 beans) on the right pan. Group C (6 beans) stays off the scale. - If the left side is heavier, the heavy bean is in Group A. - If the right side is heavier, the heavy bean is in Group B. - If they balance, the heavy bean is in Group C.
2. Weighing 2: Take the 6 suspect beans from Weighing 1. Split them into three groups of 2. Weigh Group X (2 beans) against Group Y (2 beans), with Group Z (2 beans) off the scale. - Same logic: the heavy bean is in whichever group of 2 is identified (or the unweighed group if they balance).
- Weighing 3: You now have 2 suspect beans. Place one on each pan. The heavier side contains the odd bean.
Each weighing reduces the candidate pool by a factor of 3: $18 \to 6 \to 2 \to 1$.
Answer: The minimum number of weighings is $3$. This matches the information-theoretic bound $\lceil \log_3 18 \rceil = 3$, so the strategy is optimal.
Intuition
The key principle here is that a balance scale is a ternary (base-3) information source, not binary. Each weighing has three outcomes, so it conveys $\log_2 3 \approx 1.58$ bits of information. To identify one item out of $n$, you need $\lceil \log_3 n \rceil$ weighings in the best case. The optimal strategy is always the same: divide into three groups as equally as possible, weigh two groups, and the outcome tells you which third to recurse on.
This shows up constantly in puzzle interviews and is worth internalizing as a pattern. The generalization matters too: if the odd item could be heavier OR lighter (and you don't know which), the problem becomes harder because you need to distinguish $2n$ possibilities (which bean, and which direction). That variant requires $\lceil \log_3 2n \rceil$ weighings and a more careful strategy where you track which beans have been on which side. For the simpler "known heavier" version, the pure trisection approach always works.