Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 8/28/84; site lll-crg.ARPA
Path: utzoo!linus!philabs!cmcl2!seismo!umcp-cs!gymble!lll-crg!muffy
From: muffy@lll-crg.ARPA (Muffy Barkocy)
Newsgroups: net.puzzle
Subject: Re: Weighing problem
Message-ID: <516@lll-crg.ARPA>
Date: Tue, 9-Apr-85 20:34:06 EST
Article-I.D.: lll-crg.516
Posted: Tue Apr  9 20:34:06 1985
Date-Received: Fri, 12-Apr-85 06:21:29 EST
References: <5702@duke.UUCP>
Reply-To: muffy@lll-crg.UUCP (Muffy Barkocy)
Organization: Lawrence Livermore Labs, CRG group
Lines: 25

In article <5702@duke.UUCP> aff@duke.UUCP (Amr F. Fahmy) writes:
>I am a new subscriber to net.puzzle and I don't know if the following 
>puzzle appeared before, if it did please accept my appologies.
>
>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. 
>
>This puzzle has always appealed to me very much, I don't know if there is
>a systematic way of solving it, I would be interested in case such a
>solution exists.
>
>					Amr F. Fahmy
>
>CSNet : aff@duke
>Distribution: net.puzzle


This was the first problem we did in my algorithms class this semester.
The solution can be found in COMBINATORIAL ALGORITHMS by Edward M. Reingold,
Jurg Nievergelt and Narsingh Deo, beginning on p. 14.  I will post it, if
that is desired.

                                Muffy