```Date: Jan 28, 1999 7:19 PM
Author: John Conway
Subject: Re: coins problem

Here's the solution to the n-weighing version of this problem thatI said I'd recently read.  It was found by Dyson and Lyness in 1946;I think I've improved the exposition.   I'll explain it for the originalproblem first, and then explain the generalization.     Label the 12 coins by the sequences   AAB  ABA  ABB  ABC  BBC  BCA  BCB  BCC  CAA  CAB  CAC  CCAand in the    1st                AAB ABA ABB ABC            BBC BCA BCB BCC   2nd weighings put  AAB CAA CAB CAC  in pan A, ABA ABB ABC BBC  in pan B.   3rd                ABA BCA CAA CCA            AAB ABB BCB CAB Now in a given weighing, a pan will either end up in the   Canonical position (C) that it assumes when the pans are balanced, or   Above that position (A), or   Below it (B),so the weighings determine a sequence of three of these letters.   If this sequence is CCC, then there's no fake coin.  Otherwise,for just one of the two pans the sequence is among the 12 above,and names the fake coin, whose weight is Above or Below the properone according as the pan is  A  or  B.   N weighings can be used to locate a possible fake from among(3^N - 3)/2  coins in the same way, by labelling them with allthe non-constant sequences of  N  letters from  A,B,C  whosefirst change is  A-to-B  or  B-to-C  or  C-to-A, and at thekth weighing putting those whose  kth  letter is  A  in pan A and those whose  kth  letter is  B  in pan B.                      Neat, isn't it?       John Conway
```