Date: Jan 27, 1999 9:46 PM
Author: John Conway
Subject: Re: Solution!!

I was intending to give the most-memorable solution I know to

the 12 coins problem. It was published in a poem in "Eureka",

the Cambridge University undergraduate mathematical journal,

many years ago. I the poem, the problem of finding the fake coin

was posed to Felix by his mother. He labels the coins with the

letters of

F. AM NOT LICKED

and then performs the weighings indicated by

MA DO LIKE

ME TO FIND

FAKE COIN.

It's easy to check that the 25 different cases (whether there is a

fake coin, and if so which it is, and whether it's heavy or light) all

give different answers. This solution is due to C.A.B.Smith, writing

under a pseudonym I've forgotten.

In the general case n weighings suffice to locate a fake coin

out of (3^n - 3)/2, and it's impossible to do better even though

the "information count" would allow (3^n - 1)/2. Just the other

day I read a very neat solution in a popular book by Dan Pedoe,

which is in my office so I could retail it tomorrow if anyone

would like to see it. [It's distinctly more elegant than anyone

could reasonably expect to find in a week.]

John Conway