Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: coins problem
Posted:
Jan 28, 1999 7:19 PM


Here's the solution to the nweighing version of this problem that I 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 original problem first, and then explain the generalization.
Label the 12 coins by the sequences
AAB ABA ABB ABC BBC BCA BCB BCC CAA CAB CAC CCA
and 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 proper one 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 all the nonconstant sequences of N letters from A,B,C whose first change is AtoB or BtoC or CtoA, and at the kth 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



