Eight Coins, One Heavier: Two Weighings
You have 8 identical-looking coins. Exactly one of them is heavier than the rest. You have a balance scale and may use it at most 2 times.
- Design a strategy that always identifies the heavier coin in at most 2 weighings.
- Prove that 2 weighings are sufficient (your strategy does it) and that 1 weighing is not sufficient.
Hints
- Think about how much information each weighing gives you. A balance scale has three outcomes: left heavy, right heavy, or balanced.
- Divide the coins into three groups, not two. Putting 3 coins on each side of the scale lets you narrow down to one-third of the candidates in one weighing.
- After the first weighing narrows it to 3 (or 2) coins, a single weighing of 1 vs. 1 identifies the heavy coin, since the third coin is identified by elimination if the scale balances.
Worked Solution
How to Think About It: This is an information theory problem in disguise. A balance scale has 3 possible outcomes per weighing: left side heavier, right side heavier, or balanced. So 2 weighings give you $3^2 = 9$ distinguishable outcomes. You need to identify 1 coin out of 8, which requires at least $\lceil \log_2 8 \rceil = 3$ bits -- but a balance scale gives you $\log_2 3 \approx 1.58$ bits per weighing, so 2 weighings give you $\log_2 9 \approx 3.17$ bits. That is enough to distinguish 8 possibilities, but just barely -- one weighing ($\log_2 3 \approx 1.58$ bits) is not.
The Strategy:
Label the coins 1 through 8. Divide them into three groups: - Group A: coins {1, 2, 3} - Group B: coins {4, 5, 6} - Group C: coins {7, 8}
Weighing 1: Place Group A on the left and Group B on the right (3 vs. 3).
Case 1: Left side is heavier. The heavy coin is in Group A = {1, 2, 3}.
- Weighing 2: Weigh coin 1 vs. coin 2.
- If left is heavier: coin 1 is the heavy one.
- If right is heavier: coin 2 is the heavy one.
- If balanced: coin 3 is the heavy one.
Case 2: Right side is heavier. The heavy coin is in Group B = {4, 5, 6}.
- Weighing 2: Weigh coin 4 vs. coin 5.
- If left is heavier: coin 4 is the heavy one.
- If right is heavier: coin 5 is the heavy one.
- If balanced: coin 6 is the heavy one.
Case 3: Balanced. The heavy coin is in Group C = {7, 8}.
- Weighing 2: Weigh coin 7 vs. coin 8.
- If left is heavier: coin 7 is the heavy one.
- If right is heavier: coin 8 is the heavy one.
- If balanced: impossible (one coin must be heavier).
In every case, the heavy coin is identified in exactly 2 weighings.
Proof that 2 weighings suffice: The strategy above correctly identifies the heavy coin in all 8 possible scenarios using at most 2 weighings. This is a constructive proof.
Proof that 1 weighing is not sufficient:
A single weighing of the balance scale has exactly 3 possible outcomes. Therefore, 1 weighing can distinguish among at most 3 possibilities. Since there are 8 possible locations for the heavy coin, and $8 > 3$, a single weighing cannot determine which coin is heavy. By the pigeonhole principle, at least two of the 8 coins must map to the same outcome, meaning you cannot tell them apart.
More formally: any deterministic strategy with 1 weighing is a function from {8 possible heavy coins} to {3 outcomes}. Since $8 > 3$, this function cannot be injective -- at least two coins produce the same outcome, making identification impossible.
Answer: Divide the 8 coins into groups of 3, 3, and 2. Weigh the two groups of 3 against each other. The outcome tells you which group contains the heavy coin. Then use the second weighing to identify the coin within that group (weigh 1 vs. 1, with the third deduced if balanced). One weighing is insufficient because it has only 3 outcomes but there are 8 coins to distinguish (pigeonhole principle).
Intuition
Coin-weighing puzzles are really about information theory. Each weighing of a balance scale has 3 outcomes, so $k$ weighings produce at most $3^k$ distinguishable outcomes. You can identify 1 heavy coin out of $n$ candidates if and only if $3^k \ge n$, i.e., $k \ge \lceil \log_3 n \rceil$. For $n = 8$, this gives $k \ge 2$ since $3^2 = 9 \ge 8$ but $3^1 = 3 < 8$.
The strategy of dividing into three equal (or near-equal) groups is optimal because it maximizes the information gained per weighing. Dividing into two halves (4 vs. 4) wastes the "balanced" outcome -- it can never occur when you know the heavy coin is on the scale. By dividing into thirds, every outcome narrows the candidates by a factor of 3, which is the maximum possible. This principle -- that ternary search is optimal for balance scale problems -- generalizes to larger versions (e.g., 27 coins in 3 weighings, 81 coins in 4 weighings).