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.