Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watdaisy.UUCP
Path: utzoo!watmath!watdaisy!gjerawlins
From: gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins)
Newsgroups: net.puzzle
Subject: Re: last words on coins?
Message-ID: <7201@watdaisy.UUCP>
Date: Fri, 19-Apr-85 20:17:41 EST
Article-I.D.: watdaisy.7201
Posted: Fri Apr 19 20:17:41 1985
Date-Received: Sat, 20-Apr-85 03:36:42 EST
References: <208@ihdev.UUCP>
Reply-To: gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins)
Distribution: net
Organization: U of Waterloo, Ontario
Lines: 22

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