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: Weighing Problem (solution) and new
Message-ID: <23600002@siemens.UUCP>
Date: Thu, 11-Apr-85 10:02:00 EST
Article-I.D.: siemens.23600002
Posted: Thu Apr 11 10:02:00 1985
Date-Received: Sun, 14-Apr-85 06:52:43 EST
References: <322@tekred.UUCP>
Lines: 32
Nf-ID: #R:tekred:-32200:siemens:23600002:000:1739
Nf-From: siemens!steve    Apr 11 10:02:00 1985


You couldn't be more wrong!! (insert the sound of a gong here)
Taking 1/3 vs 1/3 in the first weighing
is right, but after that you messed up!  Consider that there are 24
possible cases (12 coins * heavy or light), and three weighings can
discriminate 3^3 = 27 cases.  That means that one might possibly be
clever enough to distinguish which of 13 coins is heavy or light in
only 3 weighings, and we really ought to try hard to find a way for
12.  In the first weighing we must divide the 24 cases into three
groups each of not more than 9 cases.  1/3 vs 1/3 divides into three
sets of 8 cases each.  Now cleverly find ways of weighing coins to
divide each of those sets of 8 into sets of no more than 3 each --
I won't bother to say how because someone else already posted a solution
(which is not unique).

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