[net.puzzle] last words on coins?

rjv@ihdev.UUCP (ron vaughn) (04/19/85)

*** EGASSEM RUOY HTIW ENIL SIHT ECALPER ***

ok, let's put this coins issue to rest (i hope):

for finding a single light or heavy coin in a pile of N coins, the best
you will probably do is approximatly (big oh)  

	O(log (N))
	     3

for large N this is fairly accurate.  you have to waste about two weighings
to determine if the coin is light or heavy, and from there on out
you can break the remaining coins into three piles, and one weighing
will tell you which pile the bad coin is in.  then break THAT pile
into three etc. etc.  you reduce the size of N to 1/3N each time,
hence the running time mentioned above.

as with determining the running time of any algorithm, forget "off by
one" problems and all that garbage (*please*).  big oh is close enough.

if you turn this around, given N weighings, you should be able
to find the heaver or lighter coin in a pile of

	   3
	O(N )

coins.  again, big oh, you have to waste a couple of weighings right at
first to determine if the coin is heavier or lighter.  so this is a little 
high.


	where the hell are you people getting all these coins?? B-)


		ron vaughn	...!ihnp4!ihdev!rjv

gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins) (04/20/85)

In article <208@ihdev.UUCP> rjv@ihdev.UUCP (ron vaughn) writes:
>[......]
>if you turn this around, given N weighings, you should be able
>to find the heaver or lighter coin in a pile of
>	   3
>	O(N )
>		ron vaughn	...!ihnp4!ihdev!rjv
                             n
......Of course you meant O(3 ).
	Those interested in the general solution to this should dig
up C.A.B.Smith's article "On The Counterfeit Coin Problem",
Mathematical Gazette 1947. The are many other ways of
generalizing the problem the simplest of which is to allow *two*
(or more) counterfeit coins. The case for two was solved by
C.Christen in his paper "Optimal Detection Of Two Complementary
Defectives", SIAM J. Alg. Disc. Meth., Vol. 4 No. 1, March 1983.
The general problem in which you don't know a priori how many
counterfeit coins there are is still unsolved. Good Luck!
	greg.
-- 
Gregory J.E. Rawlins, Department of Computer Science, U. Waterloo
{allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins