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