Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site osiris.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!umcp-cs!aplvax!osiris!ken
From: ken@osiris.UUCP (Ken Harkness)
Newsgroups: net.puzzle
Subject: Re: Weighing problem
Message-ID: <229@osiris.UUCP>
Date: Wed, 10-Apr-85 15:10:56 EST
Article-I.D.: osiris.229
Posted: Wed Apr 10 15:10:56 1985
Date-Received: Fri, 12-Apr-85 07:10:50 EST
References: <5702@duke.UUCP>
Distribution: net.puzzle
Organization: Johns Hopkins Hospital
Lines: 42

> 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

The problem is solvable in a maximum of 4 uses of the balance, assuming
that you can put at least half of the weights on one side of the balance.
The solution is as follows:

(1) Put 6 on one side, 6 on the other.  One side will weigh more than 
the other.  As of yet, we do not know whether the "different" one weighs
more or less.

(2) Take the 6 on the heavier side, and balnace 3 of these against the
other 3.  If the balance is equal, then the "different" weight is in the
other set of 6, and the different weight is lighter than the other weights.
If the balance is tilted, then the "different weight is one of the 3 on
the heavier side, and is heavier than the other individual weights.
In the latter case, the problem is solved in only 3 tries.

(3) [only if (2) was equal].  Balance 3 of the other set of 6 vs its
complement.  Now take the 3 on the lighter side.

(4) With 3 weights (A,B,C) left, and knowledge of whether it is heavier
or lighter, simply balance A vs B and if (a) they balance, C is the
"different" one, (b) they don't balance, and you know it should be heavier,
or (c) they don't balance, and you know it should be lighter, choose the
appropriate weight.

Ken Harkness