Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 John Conway Posts: 2,238 Registered: 12/3/04
Re: coins problem
Posted: Feb 1, 1999 8:41 AM

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

Date Subject Author
1/27/99 Helena Verrill
1/27/99 Sarah Seastone
1/27/99 Brendan
1/27/99 John Conway
1/28/99 John Conway
2/1/99 Helena Verrill
2/1/99 John Conway
6/16/09 Barco You