The Staterion Mint case isn’t closed yet. While Liz tries to restart Kinesys, the director arrives with a pouch of twelve coins: one is fake, but this time nobody knows whether it’s lighter or heavier than the others.
“The counterfeiter has gotten worse,” Dord observes with a grimace. “At least before, he was consistent.”
The old two-pan balance is still the only instrument available, and as always, every weighing requires a permit in triplicate. Liz gives up and shuts down the engines. M00N floats above the pans, beaming: “Twelve coins, a mystery, and a balance all to ourselves. What a lovely day!”
The Riddle
With a two-pan balance, you have twelve coins, one of which has a slightly different weight from the others (you don’t know whether heavier or lighter). What is the minimum number of weighings needed to find it?
Hint
Here too, every weighing has three possible outcomes. Start by comparing two groups of four coins; in the following weighings, don’t be afraid to move coins from one pan to the other and to use coins you already know are genuine as a reference.
Solution
Three weighings are enough. Let’s call the coins A, B, C, D, E, F, G, H, I, J, K, L.
In the first weighing, compare A, B, C, D with E, F, G, H. Depending on the result, carry out the next weighings as shown in the table; the method also tells you whether the fake coin is lighter or heavier. The cases marked “impossible” can’t occur, since exactly one coin is fake.
| Weighing 1 | Weighing 2 | Weighing 3 | Fake coin |
|---|---|---|---|
| ABCD = EFGH | AI = JK | L < A | L (lighter) |
| L > A | L (heavier) | ||
| L = A | Impossible | ||
| AI < JK | J = K | I (lighter) | |
| J < K | K (heavier) | ||
| J > K | J (heavier) | ||
| AI > JK | J = K | I (heavier) | |
| J < K | J (lighter) | ||
| J > K | K (lighter) | ||
| ABCD > EFGH | AEI = BCH | F = G | D (heavier) |
| F < G | F (lighter) | ||
| F > G | G (lighter) | ||
| AEI > BCH | A = I | H (lighter) | |
| A < I | Impossible | ||
| A > I | A (heavier) | ||
| AEI < BCH | B = C | E (lighter) | |
| B < C | C (heavier) | ||
| B > C | B (heavier) | ||
| ABCD < EFGH | AEI = BCH | F = G | D (lighter) |
| F < G | G (heavier) | ||
| F > G | F (heavier) | ||
| AEI < BCH | A = I | H (heavier) | |
| A < I | A (lighter) | ||
| A > I | Impossible | ||
| AEI > BCH | B = C | E (heavier) | |
| B < C | B (lighter) | ||
| B > C | C (lighter) |
Counting outcomes confirms that three weighings are also necessary: each weighing has three outcomes, so two weighings can distinguish at most 9 situations, while here there are 24 possible cases (12 coins, each potentially lighter or heavier).