Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site ut-ngp.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!ut-sally!ut-ngp!wca
From: wca@ut-ngp.UUCP (William C. Anderson)
Newsgroups: net.puzzle
Subject: Re: Weighing problem
Message-ID: <1586@ut-ngp.UUCP>
Date: Tue, 9-Apr-85 17:43:14 EST
Article-I.D.: ut-ngp.1586
Posted: Tue Apr  9 17:43:14 1985
Date-Received: Fri, 12-Apr-85 04:45:48 EST
References: <5702@duke.UUCP>
Organization: U.Texas Computation Center, Austin, Texas
Lines: 37

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

>					Amr F. Fahmy

I don't know if this is the optimum solution, but this problem can be solved
in 4 weighings.  Method:

   1 -	Divide 12 objects into 3 piles of 4 objects each.  Label piles
	A, B, and C.

   2 -	Compare A and B. ( 1st weighing )

   3 -	Compare A and C. ( 2nd weighing )

	At this point, you now know which pile is "different", and
	whether the difference is "heavier" or "lighter".  For the
	sake of brevity, assume pile C is "different".  Then step
	2 implies that A is a "reference" pile, and step 3 will
	determine whether C is heavier or lighter.

   4 -	Divide C ( the "different" pile ) into halves and compare
	to find the "different" half. ( 3rd weighing )

   5 - 	Take the "different" half, divide into halves ( in this case,
	unit objects ) and compare.  This test determines the "different"
	object. ( 4th weighing )

I suspect that this problem has already been hashed over in net.puzzle,
but I don't recall seeing it.  Is there a way to solve this in 3 or
*fewer* weighings?

William Anderson

"Do you have a lifestyle yet?" - Zippy the Pinhead