Weighing 12 coins

The twelve coin puzzle has a long history and has been discussed in literature, periodic publications and online forums.

There are 12 coins, all identical in appearance, and all indentical in weight except for one, which is either heavier or lighter than the remaining 11 coins. Devise a procedure to identify the counterfeit coin in only 3 weighings with a balance.

There is little doubt that the puzzle can be best expressed in the ternary system. There is one solution due to Dyson and Lyness that makes the most explicit use of the number representation in the ternary. This solution has been discussed by Dan Pedoe in his wonderful book and John Conway on an online forum.

Conway, like B. Bundy before him, uses mnemonic notations apparently to clarify the solution. The labeling of coins in a 3-letter alphabet may indeed be arbitrary, but when it's explicit, like in the original solution by Dyson and Lyness, the relevance of the ternary system becomes even more ample.

Following Conway, label coins by the sequence

(1) AAB ABA ABB ABC BBC BCA BCB BCC CAA CAB CAC CCA

and think of C as related to the canonical (balanced) position, while A and B represent the above and below positions, respectively.

The coins for the three weighings are selected in a simple and uniform manner. For the ith weighing, place the coins whose label has an A in the ith position in pan A, and those with B in the ith position in pan B:

 1:  AAB ABA ABB ABC | BBC BCA BCB BCC
(2)2:  AAB CAA CAB CAC | ABA ABB ABC BBC
 3:  ABA BCA CAA CCA | AAB ABB BCB CAB

The results of the weighings are recorded in order to produce a three letter label. If the pans balance in the ith weighing, write C in the ith position. If pan A is up, write A. If pan B is up, write B. There are now two possibilities (something that has been overlooked by Conway): the label thus obtained is one among those listed in (1), or it is not. In the former case, the label points to a certain coin, the one coin that bears this label. This is a fake coin and it is lighter than normal.

If the resulting label does not appear in (1) it need to be replaced with a corresponding "conjugate" label out of (in the proper order)

(3) BBA BAB BAA BAC AAC ACB ACA ACC CBB CBA CBC CCB,

where, compared to (1), A replaced B, and vice versa. If the resulting label appears in (3), the coin with the counterpart label in (1) is fake and is heavier than normal.

Together (1) and (3) list 24 combinations. 24 combinations out of possible 27 = 33. Three labels - AAA, BBB, CCC - have been omitted. CCC would mean that there was no fake coin, to start with. What about AAA and BBB? As has been mentioned by B. Bundy, but skirted by Conway and Pedoe, the distribution (2) of coins in the pans is such that no coin appears three times in the same pan in all three weighings. Therefore, the two constant labels - AAA and BBB - could never be obtained.

The solution by Dyson and Lyness adds a nice touch to the assignment of labels in (2). In the (balanced) ternary system that uses digits -1, 0, 1 the twelve numbers 1, 2, ..., 12 are represented as

(4)
1  001  CCA  CCB
2  01(-1)  CAB  CBA
3  010  CAC  CBC
4  011  CAA  CBB
5  1(-1)(-1)  ABB  BAA
6  1(-1)0  ABC  BAC
7  1(-1)1  ABA  BAB
8  10(-1)  ACB  BCA
9  100  ACC  BCC
10  101  ACA  BCB
11  11(-1)  AAB  BBA
12  110  AAC  BBC

In the righ two columns, 0 has been replaced with C, whereas 1 and -1 has been replaced with A and B in one column and with B and A in the other. The distribution of the 24 labels in (4) between the sequences (1) and (3) follows the following rule. If the first change of letters in a string is from A to B or B to C or C to A, the label goes in (1); otherwise, it goes in (2).

As an example (see also Steinhaus's Snapshots), 8 = 1·9 + 0·3 + (-1)·1. It therefore is associated with labels ACB and BCA. If the three weighings record either ACB or BCA, the 8th coin is a fake and is lighter than normal, for ACB, and is heavier than normal, for BCA.

References

  1. F. J. Dyson and R. C. Lyness, in Math. Gazette, v 30, Oct. 1946
  2. D. Pedoe, The Gentle Art of Mathematics, Dover, 1973
  3. F. Schuh, The Master Book of Mathematical Recreations, Dover, 1968, p 307
  4. H. Steinhaus, Mathematical Snapshots, umpteen edition, Dover, 1999
[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
[an error occurred while processing this directive]