Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: $Revision: 1.6.2.14 $; site siemens.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!princeton!siemens!steve
From: steve@siemens.UUCP
Newsgroups: net.puzzle
Subject: Re: Advanced Weighing problem
Message-ID: <23600003@siemens.UUCP>
Date: Fri, 19-Apr-85 08:52:00 EST
Article-I.D.: siemens.23600003
Posted: Fri Apr 19 08:52:00 1985
Date-Received: Sat, 20-Apr-85 03:21:13 EST
References: <455@alberta.UUCP>
Lines: 26
Nf-ID: #R:alberta:-45500:siemens:23600003:000:1289
Nf-From: siemens!steve    Apr 19 08:52:00 1985


I already answered this question, but it's quite possible my response
never made it out to the net.  Here's the relevant part:

> /* Written 10:02 am  Apr 11, 1985 by steve@siemens in siemens:net.puzzle */
> 
> To prove you cannot distinguish which one is heavy or light from 13
> coins, in three weighings.  The first weighing must split the 26 cases
> into three sets of no more than 9 cases each.
(Because the following two weighings can distinguish at most 9 cases.)
> It must be a weighing of
> n coins against n coins, and will divide the 26 cases into 2n, 26-2n,
> and 2n cases for outcomes of <, =, and > respectively.  For no integral
> value of n is 2n <= 9 and 26-2n <= 9.  Therefore there is no way to
> determine which of 13 coins is heavy or light in 3 weighings.
> 
> In fact, by just looking at the first weighing you can show by a
> generalization of the proof above that for w weighings, an upper bound on
> the number of coins you can distinguish is
> 	(3^w - 3)/2
> (which is an integer), and the first weighing must be 1/3 vs 1/3 of
> those coins, which is also integral.  Can you actually find the bad coin
> (and whether it is heavy or light) from 39 coins in 4 weighings?
> 
> Steve Clark      ...princeton!siemens!steve
> /* End of text from siemens:net.puzzle */