Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Math Topics » geometry.puzzles.independent

Topic: coins problem
Replies: 7   Last Post: Jun 16, 2009 10:34 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
John Conway

Posts: 2,238
Registered: 12/3/04
Re: coins problem
Posted: Jan 28, 1999 7:19 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.