Doc/Articles/Play183
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
29. The Counterfeit Coin Problem
. By Eugene McDonnell. First published in Vector, 18, 3, (January 2002), 93-103.
The Counterfeit Coin Problem, unlike many mathematical puzzles, is not a creation of ancient times nor of the 19th century, and does not appear in the classical works of Loyd, Dudeney, Ball, or Kraitchik. It springs from a problem posed by E. D. Schell in the January 1945 issue of the American Mathematical Monthly:
You have eight similar coins and a beam balance. At most one coin is counterfeit and hence underweight. How can you detect whether there is an underweight coin, and if so, which one, using the balance only twice?
Try solving this. I give my solution at the end of this paper.
Most of the solutions I have seen for this kind of problem give an initial allocation of the coins to the balance’s pans, and on the basis of the weighing give another allocation, and so on. In 1978 J. G. Mauldon published an IBM Research Report RC 7476, in which he gave a solution in which the weighings were predetermined, not a result of a previous weighing, entitled “Strong Solutions for the Counterfeit Coin Problem”. His statement of the problem is generalized from Schell’s. I’ll call this the first problem:
Given C coins, of which it is suspected that one (at most) is counterfeit (either underweight or overweight), it is required, in at most W weighings on an ordinary beam balance, to identify the counterfeit (if present) and to determine whether it is heavy or light.
He defines a strong solution to which “The choice and distribution of coins for each weighing is to be independent of the other weighings.” In support of his method, he proves the theorem that “if the pair (W,C) admits a solution at all, then it admits a strong solution.” Thus, no other solution can be better than his strong technique. His method is array oriented, and he gives a suite of APL direct definition functions which give a solution to the problem, acknowledging “his indebtedness to the encouragement and valuable advice of Dr. Kenneth Iverson.” He also gives solutions for a second problem, where we are given that exactly one coin is counterfeit, and we are not required to specify whether it is heavier or lighter, but merely to identify it, and a third problem in which in addition to the given set of coins, we are allowed to incorporate into the weighings an arbitrary number of coins known to be of standard weight. I’ll only discuss the first problem. His solutions to all three problems are similar.
He defines a solution as a table of weighings showing the allocation of coins at each weighing. In table (A) are his solutions for all nine cases for which W is 3. These are for values of C from 4 through 12, inclusive.
C = 4, 7, 10 C = 5, 8, 11 C = 6, 9, 12 +-------------------+---------------------+-----------------------+ |0 0 1 2 |1 1 0 2 2 |0 1 2 0 1 2 | |0 2 1 0 |1 2 2 1 0 |0 1 2 1 2 0 | |1 0 0 2 |2 1 2 1 0 |1 2 0 0 1 2 | +-------------------+---------------------+-----------------------+ |0 1 2 0 0 1 2 |2 0 1 1 1 0 2 2 |0 1 2 0 1 2 0 1 2 | |1 2 0 0 2 1 0 |2 1 0 1 2 2 1 0 |0 1 2 1 2 0 1 2 0 | (A) |2 0 1 1 0 0 2 |2 0 1 2 1 2 1 0 |1 2 0 0 1 2 1 2 0 | +-------------------+---------------------+-----------------------+ |0 1 2 0 1 2 0 0 1 2|0 1 2 2 0 1 1 1 0 2 2|0 1 2 0 1 2 0 1 2 0 1 2| |1 2 0 1 2 0 0 2 1 0|1 2 0 2 1 0 1 2 2 1 0|0 1 2 1 2 0 1 2 0 1 2 0| |1 2 0 2 0 1 1 0 0 2|2 0 1 2 0 1 2 1 2 1 0|1 2 0 0 1 2 1 2 0 2 0 1| +-------------------+---------------------+-----------------------+
Mauldon calls the solution for twelve coins maximal. A maximal solution is one in which C is the largest number of coins admitting a solution for a given W. Solutions for less than the maximal number of coins he calls submaximal. He tackles maximal solutions first, for these are used in forming submaximal solutions as well.
Each solution has three rows, one for each of the three weighings, and four through 12 columns, one for each of the coins. Each row gives an allocation of the coins as being either set aside, or put in the left pan, or put in the right pan, represented by 0, 1, or 2, respectively. Notice that in each weighing the number of coins placed on the left pan is the same as the number placed on the right pan, that is, the solutions are balanced. For example, in the four-coin case the first weighing sets aside coins 0 and 1, puts coin 2 in the left pan, and coin 3 in the right pan. When 3|C is one, that is, for C of 4, 7, and 10, the number of coins set aside is one more than the number on each pan. When 3|C is 2, for C of 5, 8, and 11, the number of coins set aside is one less than the number on each pan. When 3|C is 0, as in the right column, for 6, 9, and 12, the number of coins set aside is the same as the number on each pan. At each weighing, the possible results are: the pans are level, or the left pan is lower, or the right pan is lower, represented by 0, 1, and 2, respectively. The result of all three weighings is thus a list V of three items, chosen from 0 1 2.
For example, if there are four coins, and the counterfeit is coin 0, and is heavier than a good coin, the result of the first weighing is 0, since coin 0 is set aside; for the same reason, the result of the second weighing is also 0; in the third weighing coin 0 is in the left pan, so the result is 1. The overall result V is thus 0 0 1, and this corresponds to column 0 of the 4-coin solution. Additional complications come about if the counterfeit is lighter, for which table (B) is appropriate:
+-------------------+---------------------+-----------------------+ |0 0 2 1 |2 2 0 1 1 |0 2 1 0 2 1 | |0 1 2 0 |2 1 1 2 0 |0 2 1 2 1 0 | |2 0 0 1 |1 2 1 2 0 |2 1 0 0 2 1 | +-------------------+---------------------+-----------------------+ |0 2 1 0 0 2 1 |1 0 2 2 2 0 1 1 |0 2 1 0 2 1 0 2 1 | |2 1 0 0 1 2 0 |1 2 0 2 1 1 2 0 |0 2 1 2 1 0 2 1 0 | (B) |1 0 2 2 0 0 1 |1 0 2 1 2 1 2 0 |2 1 0 0 2 1 2 1 0 | +-------------------+---------------------+-----------------------+ |0 2 1 0 2 1 0 0 2 1|0 2 1 1 0 2 2 2 0 1 1|0 2 1 0 2 1 0 2 1 0 2 1| |2 1 0 2 1 0 0 1 2 0|2 1 0 1 2 0 2 1 1 2 0|0 2 1 2 1 0 2 1 0 2 1 0| |2 1 0 1 0 2 2 0 0 1|1 0 2 1 0 2 1 2 1 2 0|2 1 0 0 2 1 2 1 0 1 0 2| +-------------------+---------------------+-----------------------+
The entries in (B) are not used for allocating the coins, but rather to determine the false coin when it is lighter than the good coins. For example, if their are four coins, and the false coin is coin 0, and is lighter than the others, the result would be 0 0 2, corresponding to column 0 of the 4-coin table in (B). The tables in (B) are the 3s complement of those in (A).
The table below gives some of the vital statistics of the problem:
+-+----+----+----+ |W| N | L | G | +-+----+----+----+ |3| 9| 4| 12| |4| 27| 13| 39| |5| 81| 40| 120| |6| 243| 121| 363| |7| 729| 364|1092| |8|2187|1093|3279| +-+----+----+----+
Column W gives the number of weighings required, column N gives the number of different cases that W weighings can solve, column L gives the least number of coins for W, and column G gives the greatest number of coins for W. For example, if W is four, 27 cases are solvable, with 13 coins the smallest case, and 39 coins the largest. I don’t show the case for W of 2, since three is the only meaningful case. A one-coin case admits of no comparisons, and a 2-coin case can’t discriminate between heavier and lighter coins.
Given any number of coins K between L and G inclusive, W may be found from K by taking the ceiling of the base-3 log of 3 plus twice K:
WK =: >.@(3&^.)@(3&+)@(2&*) WK 4+i.9 3 3 3 3 3 3 3 3 3 WK 13+i.27 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
N is a power of three, namely 3^W-1, and is included between L and G, and is the only power of 3 included. Column L is the sum-scan of powers of 3; the first item is 1+3, the second is 1+3+9, and so forth. Column G is thrice column L, and is also given by
((3^W)-3)%2 [ W=: 3 4 5 6 7 8 12 39 120 363 1092 3279
Given any positive integer q greater than one, its representation in base q has 1 as its most significant digit (msd), and is in fact 10. For any q greater than 2, its double is represented in base q by 20. Its square is 100 and the square’s double is 200. Its cube is 1000, and so forth. All the numbers from q up to but not including its double have msd of 1. All the numbers from p any power of q up to but not including its double have msd of 1. For example, the ternary representations 1 and 2 are 1, 2; of 3, 4, 5, 6 are 10, 11, 12, 20; of 9 through 18 are:
100 101 102 110 111 112 120 121 122 200
There are L integers less than N that have msd of 1. For example, if W is 3, then N is 9 and there are 4 ternary integers with msd 1 less than 9; these are 1, 3, 4, and 5, which have ternary representations of 1, 10, 11, and 12. When represented in a radix large enough to represent N, the msd numbers have leading zeros. For example, 9 is represented by 100, and those for 1, 3, 4, and 5 are then 001, 010, 011, and 012.
Constructing a maximal solution
We’ll use the case where W is 3 to exemplify the general case.
Start with the ternary representations of the msd numbers less than 3^W-1. In our case these are 1 3 4 5.
First we produce the powers of 3 less than 3^W-1:
W =: 3 3 ^ i. <: W 1 3
Next we use the hook (+i.) with each of these:
(+ i.) &.> 3 ^ i. <: W +-+-----+ |1|3 4 5| +-+-----+
Last, we raze this:
; (+ i.) &.> 3 ^ i. <: W 1 3 4 5
We convert these to ternary, getting four distinct representations:
] za =: (W # 3) #: ; (+ i.) &.> 3 ^ i. <: W 0 0 1 0 1 0 0 1 1 0 1 2
Each row of za is used to create two additional rows by adding 1 and 2, mod 3, to it. Adding 1, mod 3, to 0 1 2 gives 1 2 0; adding 2 to 0 1 2 gives 2 0 1. Consequently each three-row subtable has distinct rows. Notice that each column is also balanced, having one each of 1 and 2.
] zb =: 3|0 1 2+/"1 za 0 0 1 1 1 2 2 2 0 0 1 0 1 2 1 2 0 2 0 1 1 1 2 2 2 0 0 0 1 2 1 2 0 2 0 1
This is turned into a single table by applying append insert (,/) to it. Since the individual columns of the subtables were balanced the whole column is also balanced. In this case each weighing places four coins in each pan.
,/ zb 0 0 1 1 1 2 2 2 0 0 1 0 1 2 1 2 0 2 0 1 1 1 2 2 2 0 0 0 1 2 1 2 0 2 0 1
I’ll transpose this to allow you to more easily to compare with the lower right-hand corner of table (A):
] zc =: |: , / 3 | 0 1 2 +/ "1 zb 0 1 2 0 1 2 0 1 2 0 1 2 1 2 0 1 2 0 1 2 0 1 2 0 2 0 1 2 0 1 2 0 1 2 0 1 0 1 2 1 2 0 1 2 0 1 2 0 1 2 0 2 0 1 2 0 1 2 0 1 2 0 1 0 1 2 0 1 2 0 1 2 1 2 0 0 1 2 1 2 0 2 0 1 2 0 1 1 2 0 2 0 1 0 1 2 0 1 2 2 0 1 0 1 2 1 2 0
The entire maximal solution process can be encapsulated in monad SX, which takes the number of weighings as argument.
SX =: 13 : ',/ 3 | 0 1 2 +/"1 (y # 3) #: ; (+ i.) &.> 3 ^ i. <: y' |: SX 3 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 1 2 0 1 2 0 1 2 0 1 2 0 0 1 2 1 2 0 2 0 1
Constructing a general solution
Mauldon’s method of obtaining a general solution involves a fairly complicated way of choosing one of two tables to be appended, in the cases where the number of coins has a 3-residue of 1 or 2, or no appended table for the case where the 3-residue is 0. It simplifies things considerably if a third, empty table, is provided for this last case. If we call the appended tables A0, A1 and A2, for residues of 0, 1 and 2, respectively, and form them into a list of boxes AS. Mauldon doesn’t give the principles used in constructing A1 and A2, he merely presents them without apology.
A0 =: 0 3 $ 0 A1 =: 4 3 $ 0 0 1 0 2 0 1 1 0 2 0 2 A2 =: 8 3 $ 2 2 2 0 1 0 1 0 1 1 1 2 1 2 1 0 2 2 2 1 1 2 0 0 ] AS =: A0;A1;A2 +---+-----+-----+ | |0 0 1|2 2 2| | |0 2 0|0 1 0| | |1 1 0|1 0 1| | |2 0 2|1 1 2| | | |1 2 1| | | |0 2 2| | | |2 1 1| | | |2 0 0| +---+-----+-----+
Each of these is balanced, and the last five rows of A2 are also balanced. If K is the number of coins in C, the proper table to append can be given by:
> AS {~ 3 | K [ K =: 5
2 2 2
0 1 0
1 0 1
1 1 2
1 2 1
0 2 2
2 1 1
2 0 0
This isn’t all that is needed. The three columns in the tables are suited to the least number of weighings that may be required. If more weighings than three are needed, the first column is replicated W-2 times. For example, if W is 5 there are five weighings and the first column is replicated thrice:
(((W-2)#0), 1 2){"1 A2 [ W =: 5
2 2 2 2 2
0 0 0 1 0
1 1 1 0 1
1 1 1 1 2
1 1 1 2 1
0 0 0 2 2
2 2 2 1 1
2 2 2 0 0
A dyad SA to produce a table to append having the necessary number of columns can thus be given by:
SA =: 13 : '(((y-2)#0),1 2){"1>AS{~3|x'
where x is the number of coins and y is the number of weighings.
The two dyads SX and SA can be combined to give a general solution function SG:
SG =: 13 : '(-x){.x(SX,SA)y'
where x and y are as in SA. The phrase (-x){ forms the solution by taking the last x rows of the table formed by appending the maximum and the appended tables.
A solution for the case of 8 coins and 3 weighings can be obtained by:
8 SG 3 2 2 2 0 1 0 1 0 1 1 1 2 1 2 1 0 2 2 2 1 1 2 0 0
I found it convenient to have a monad which takes a list of coins as argument. The monad is:
SC =:(SG WK)@# C =: 0 0 0 0 0 1 0 0 ] S =: SC C 2 2 2 0 1 0 1 0 1 1 1 2 1 2 1 0 2 2 2 1 1 2 0 0
Finding a false coin
We can find a solution by writing:
S+//."1&.|:C
The dual transpose (&. |:) causes the arguments to be transposed before being used. This has no effect on the coin list C, but is effective on S, interchanging columns and rows. The rank one ("1) allows the rows of transposed S to be used individually with C. The sum by key (+//.) adds the items of C according to the keys in the row of transposed S. The result of sum key of the first row with C is:
2 0 1 1 1 0 2 2 +//. 0 0 0 0 0 1 0 0 0 1 0
The result comes from summing all the items of the right argument corresponding to 2s in the left argument (0), then those corresponding to 0s (1) then those corresponding to 1s (0).
The same thing occurs when I use all the rows of transposed S with C:
S +/ /."1 &. |: C 0 1 1 1 0 0 0 0 0
This is difficult to interpret because the first column 0 1 0 is in the order 2 0 1, the order in which they occur in the first column of S; the second column 1 0 0 is in the order 2 1 0; the third column is in the order 2 0 1.
In order to avoid this difficulty, I prefix the solution rows (transposed columns) with 0 1 2 and the coin list with 0 0 0. The prefixed zeros on the coin list can’t alter the result, but the 0 1 2 prefixed to the columns ensures that the result comes in a way that is easy to interpret.
] zr =: }. S (0 1 2&,@[ +//. 0 0 0&,@])"1&.|: C 0 0 0 0 1 1
I drop the first row of the result, which corresponds to the coins set aside, because in the physical experiment these are not seen. The table zr is interpreted thus: the rows correspond to left pan and right pan, and the columns correspond to weighings. In the first weighing the left and right pans were level. In the second and third weighing the right pan was lower.
Now, if I take the difference of the left and right pan rows I get:
-/}.S (0 1 2&,@[ +//. 0 0 0&,@])"1&.|: C 0 _1 _1
And I need the 3s-complement of this:
3|-/}.S (0 1 2&,@[ +//. 0 0 0&,@])"1&.|: C 0 2 2
This tells me that in the first weighing the pans were level, and in the last two the right pan was lower.
The dyad WR encapsulates the preceding steps:
WR =: 13 : '3|-/ }. x (0 1 2&,@[ +//. 0 0 0&,@])"1&.|: y' ] WL =: S WR C 0 2 2
The next step is to find the index of WL in either S or its 3s complement. The 3s complement is formed by taking the 3 residue of -S.This is laminated (,:) to S, forming SC:
] SC =: (,:3&|@-)S 2 2 2 0 1 0 1 0 1 1 1 2 1 2 1 0 2 2 2 1 1 2 0 0 1 1 1 0 2 0 2 0 2 2 2 1 2 1 2 0 1 1 1 2 2 1 0 0
By using rank 2 1 with the index of function. we can obtain the indices in both planes of SC:
SC i."2 1 WL 5 8
Since there are 8 items in each of the tables, the result 5 8 means that the weighing list was found in item 5 of the first table, and not at all in the second. This sequence is encapsulated in dyad WI:
WI =: 13 : '((,:3&|@-)x)i."2 1 y' S WI WL 5 8
This has all the information needed for the answer. The index is clearly the smaller of the two values. The heavier or lighter indication is given by whether the index is in the first or second table: if in the first, it is heavier; if in the second it is lighter. The final result can thus be given by RW:
RW =: 13 : '((<./y),({&_1 1)</y)'
RW 5 8
5 1
This says that coin 5 is false, and it is heavier than a good coin.
To complete the problem, it would be necessary to provide for the case where there isn’t a false coin. What happens then?
S WI 0 0 0 8 8 RW 8 8 8 _1
So the result when there is no false coin is an impossible index and a lighter coin indication.
Solution to Schell’s Problem
Assume the eight coins are labeled A B C D E F G H. Then the steps below show how to solve the problem with two weighings. The first column gives the step number, and the next two columns give the allocation of coins to pans. The three columns at the right indicate the result of the weighing. After step 1, only one of either step 2 or step 3 or step 4 is executed. Each of these steps has 3 possible outcomes. For example, if the result of step 1 is “right pan high”, go to step 3, which tells us to place coin D in the left pan and coin E in the right pan. If the left pan is now high, this means that D is the false coin, and so forth.
step left pan right pan left pan high right pan high pans level 1 A B C D E F go to step 2 go to step 3 go to step 4 2 A B A B C 3 D E D E F 4 G H G H none