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
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.
- F. J. Dyson and R. C. Lyness, in Math. Gazette, v 30, Oct. 1946
- D. Pedoe, The Gentle Art of Mathematics, Dover, 1973
- F. Schuh, The Master Book of Mathematical Recreations, Dover, 1968, p 307
- H. Steinhaus, Mathematical Snapshots, umpteen edition, Dover, 1999
Copyright © 1996-2018 Alexander Bogomolny