Date: Feb 1, 1999 8:41 AM
Author: John Conway
Subject: Re: coins problem

On Mon, 1 Feb 1999, Helena Verrill wrote:

> By the way, you said that an information count would make you

> think you could do (3^n-1)/2 --- I suppose you mean that there are 3

> possibilities for weighing, so n weighing gives 3^n outcomes,

> and k coins means 2k possibilitis, (anyone light or heavy),

I'd prefer to note the all-balanced case can't happen if there's

a fake coin, but does happen if there's no fake, which increases

the number of possibilities to 2k+1.

> so, max k has 2k=3^n, and since that k is not an integer,

> you get (3^n-1)/2.... so how do you prove you can't do this many?

I found a very easy argument to prove this when I considered this

problem as a student, but can't remember it at this moment.

> And why is it, that if you just have the extra information

> that you know the odd coin is light, then the 'information

> count' does work, and you can do 3^n in n weightings?

> what's the difference?

Since 3^n is what you'd expect, it requires no explanation,

unlike (3^n - 3)/2, for which I'll try to reconstruct the

argument.

John Conway