All true coins have the same weight, a false coin is too heavy or too
light. Given (3` ^{n}`-1)/2 coins of which at most 1 coin is
false, we have to determine whether they are all true, and, if not, we
have to identify the false coin and to determine whether it is too
heavy or too light. Our equipment consists of an additional coin
known to be true and a balance that may be used for n weighings.

Let us denote (3` ^{n}`-1)/2 by

Our first weighing involves 2∙`s.n` + 1 of the coins to be investigated. With the balance we compare `s.n`+1 of those with the other `s.n`, complemented with the coin known to be true.

If the two sets are of equal weight, we use the remaining `n` weighings to solve the problem for the `s.n` coins that have not been on the balance yet.

If the two sets are of different weight, we have 2∙`s.n` + 1 suspect coins, more precisely, `s.n`+1 suspects of the one polarity and `s.n` suspects of the other polarity. We make `s.n` “double coins” by pairing suspects of different polarity; this leaves one suspect of known polarity unpaired. We now use the remaining `n` weighings to solve the problem for the `s.n` “double coins”. If all double coins are “true”, the unpaired suspect (whose polarity is known) is the false coin. If one of the double coins is “false”, the polarity of its falseness determines which of its two constituent suspects is the false coin.

__Note__ For `n`>0, `s.n` ≥ 1. In that case we have enough —i.
e. 2— coins known to be true to make a true “double coin” when we need it. (End of Note.)

The above takes care of the induction step. For the base it suffices to observe that s.0=0 and that for 0 coins, 0 weighings suffice to determine that all the coins are true.

* *

*

Variations of this problem circulated in the United Kingdom during WWII, and after the war in the rest of Europe — e.g. 12 coins, one of which is false, 3 weighings, but no 13th coin known to be true. It surfaced this week in the department and turned out to be new for my graduate students. The reason that I took the trouble of writing down the above, is that it provides a nice example of a forced argument.

With `s.n` possibilities for the false coin, 2 possibilities for the polarity of its falseness, + the possibility of all coins true, our weighing algorithm has to distinguish between 2∙`s.n` + 1 cases. But, 2∙`s.n` + 1 being equal to 3` ^{n}`, and a weighing having 3 possible outcomes, the

In other words: faced with `s`.(`n`+1) coins, for which we have to distinguish between 3^{n}^{+1} cases, each outcome of the first weighing has to reduce the number of possibilities to 3` ^{n}`, no more and no less. Hence the number of coins not involved in the first weighing (which can imply: no false coin on the balance) has to be

Austin, 1 September 1990

prof. dr. Edsger W. Dijkstra

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712-1188

USA