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?

John Conway