Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84 exptools; site ihdev.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!ihnp4!ihdev!rjv
From: rjv@ihdev.UUCP (ron vaughn)
Newsgroups: net.puzzle
Subject: last words on coins?
Message-ID: <208@ihdev.UUCP>
Date: Fri, 19-Apr-85 00:03:50 EST
Article-I.D.: ihdev.208
Posted: Fri Apr 19 00:03:50 1985
Date-Received: Sat, 20-Apr-85 01:45:17 EST
Distribution: net
Organization: AT&T Bell Laboratories
Lines: 35

*** 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