Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 (Tek) 9/26/83; site tekred.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!houxm!vax135!cornell!uw-beaver!tektronix!tekred!ronbe
From: ronbe@tekred.UUCP (Little Guy)
Newsgroups: net.puzzle
Subject: Weighing Problem (solution) and new puzzle
Message-ID: <322@tekred.UUCP>
Date: Wed, 10-Apr-85 15:48:39 EST
Article-I.D.: tekred.322
Posted: Wed Apr 10 15:48:39 1985
Date-Received: Thu, 11-Apr-85 07:34:14 EST
Organization: The Hollow Tree
Lines: 46

-> Given 12 identical items all weighing the same but only
-> one is "different" in weight from all the others.  You
-> are given a balance (no weights), a pen (just in case you
-> need to mark items) and nothing else to use. You are asked
-> to identify the different item using the balance the least
-> number of times. 

	The puzzle is easy if you know that the odd object
is heavier or lighter than the others.  The odd one can be
found in three weighings consistently.  Just divide the group
in thirds, and put two of the thirds on the balance.  If it
balances, you've eliminated all objects on the balance.  If
not, you've eliminated the other third and (providing you
know that the odd one is heavier), one of the groups that are
on the balance.  The same three weighings can be used to find
the heavy object in 27.
	Things get a little trickier when one doesn't know
that the odd object is heavier or lighter.  I'd still take
the same approach.  Weigh 1/3 against 1/3.  If the scale
balances, you've eliminated 2/3 of the objects.  If not, you've
eliminated 1/3.  This method could be used recursively with
large numbers of objects.  The last check would be with the
odd object (and possibly one other) against one (or two)
eliminated (equal) objects to determine if the left-over
object was heavy or light.  At worse, you will eliminate
int(x/3) objects each time.  (x is the number of un-
eliminated objects left.  At worst, this will take 7
weighings:  (e=eliminated -even- object)
1)  4 - 4	eliminates at least 4 (8 left)
2)  2 - 2	eliminates at least 2 (6 left)
3)  2 - 2	eliminates at least 2 (4 left)
4)  1 - 1	eliminates at least 1 (3 left)
5)  1 - 1	eliminates at least 1 (2 left)
6)  1 - e	eliminates 1 (1 left)
7)  1 - e	determines heavy/light
At best, it could take 3 weighings:
1)  4 - 4	eliminates at most 8 (4 left)
2)  1 - 1	eliminates at most 2 (2 left)
3)  1 - e	could determine heavy/light
	Perhaps a better puzzle would be to find the probability
of finding the odd object in 3, 4, 5, 6, or 7 weighings.

	Send those replies!
-- 
Support bacteria - It's the only culture some people have!
	...tektronix!tekred!ronbe (Ron Bemis)