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