A few days ago I posted on a problem (Problem 4(a) on Page 7) from the very nice The USSR Olympiad Problem Book, by D.O. Shklarsky, N.N. Chentzov, and I.M. Yaglom:
We are given 80 coins of the same denomination; we know that one of them is counterfeit and that it is lighter than the others. Locate the counterfeit coin by using four weighings on a pan balance.
Problem 4(b) asks readers to generalize this problem if there are n coins instead of 80; that is, what is the minimum number of weighings needed in general?
Discussion towards a solution:
OK, let’s put 40 coins on each pan of the balance. The lighter pan contains the counterfeit coin, so we can take this group of 40 coins, separate it into two groups, and put each group of 20 coins on the pans. Once again, we focus attention on the lighter pan, and repeat the process. In summary:
| Weighing # | 1 | 2 | 3 | 4 |
| Weighing | 40 vs 40 | 20 vs 20 | 10 vs 10 | 5 vs 5 |
OK, so this fails because we’ve used our 4 weighings and at the end we still have 5 coins left under consideration. Also, it’s clear that each weighing reduces the number of coins under consideration by a factor of 2, so it seems that if the number of coins is a power of 2 that is good. So maybe we should divide the initial number of coins according to powers of 2; for example, what if we balance 32 coins against 32 in the first weighing; if we luck out and get a balance, then we know the counterfeit coin is one of the 16 leftovers that were not part of the first weighing. If the pans don’t balance in the first weighing, then we get:
| Weighing # | 1 | 2 | 3 | 4 |
| Weighing | 32 vs 32 | 16 vs 16 | 8 vs 8 | 4 vs 4 |
This still doesn’t work because we would be left with 4 coins under consideration after the fourth weighing.
OK, I’m stuck and have no idea what to do next. A good strategy to use when you’re stuck is to
solve a simpler problem.
OK, when you’re dealing with a problem involving a certain number of things, such as the 80 coins here, try to solve the analogous problem with a fewer number of the things. So let’s see how to solve the problem when there are 2 coins, where one coin is known to be lighter than the other. Only 1 weighing is needed.
What if there are 3 coins, and one coin is known to be lighter than the others? Balance one coin against another, leaving the third coin aside for a moment. If the two coins do not balance, the lighter one is the counterfeit. If they do balance, then the leftover coin is the counterfeit.
Ah! We had three coins, but we only needed one weighing to determine the counterfeit coin. Evidently we were helped by knowing that the counterweight coin is underweight; otherwise a second weighing would have been necessary if the first weighing were unbalanced.
So perhaps we should divide the number of coins as equally as possible into groups of three? For example, if there are nine coins to start with, then we balance three against three. If the first weighing is unbalanced, restrict attention to the lighter group of three. If the first weighing is balanced, restrict attention to the leftover group of three. In either case, after one weighing we have eliminated two-thirds of the coins from consideration.
So, with 80 coins, we proceed as follows:
| Weighing # | 1 | 2 | 3 | 4 |
| Weighing | 27 vs 27 | 9 vs 9 | 3 vs 3 | 1 vs 1 |
If at the first stage we must restrict attention to the leftover group, which has only 26 coins, we can always toss in a coin from the known “good” coins to make up 27, if we wish.
One can see that the problem posers were careful to stay away from 81, which is a power of 3, to avoid giving the game away! And it’s also interesting to note that for a two-pan balance, we separate the coins into groups of 3, because 3 = 2 + 1. If there existed some kind of magical m-pan balance, that would balance m arms and indicate which of the arms was lighter or heavier, all others being equal, the optimal strategy would be to separate the coins into m + 1 groups.
In general, for n coins, it is possible to show that k weighings are sufficient, where k is the unique natural number such that
$3^{k – 1} < n \le 3^k$
The proof that this choice is optimal is in the book, and I’ll let interested readers check their own proof against the authors’ proof.
(This post first appeared at my other (now deleted) blog, and was transferred to this blog on 21 January 2021.)