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 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 non-constant sequences of N letters from A,B,C whose
first change is A-to-B or B-to-C or C-to-A, 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?