Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/3/84; site talcott.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!bellcore!decvax!genrad!panda!talcott!gjk
From: gjk@talcott.UUCP (Greg Kuperberg)
Newsgroups: net.puzzle
Subject: Re: Weighing problem (Unrotated solution)
Message-ID: <403@talcott.UUCP>
Date: Wed, 10-Apr-85 01:13:27 EST
Article-I.D.: talcott.403
Posted: Wed Apr 10 01:13:27 1985
Date-Received: Fri, 12-Apr-85 00:00:01 EST
References: <5702@duke.UUCP>
Distribution: net.puzzle
Organization: Harvard
Lines: 58

> 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

It's pretty obvious that you can't do this problem in two weighings; I
won't go through the tedium of demonstrating it.  However, there is a
way to do it in three, yes *three* weighings.  Here's how:

1.  Divide the weights into three piles of four.  Weigh the one group of
four against another.  If they are equal, go to step 6.  If they are
unequal, proceed to step 2.

2.  I'll call one pile the heavy pile, the other the light pile, and the
third the neutral pile.  Take three weights from the heavy pile and one
from the light pile and weigh them against the fourth heavy weight and
three neutral weights.  If the side with three neutrals is heavier, go to
step 3.  If the two sides are equal, go to step 4.  If the side with three
heavies is heavier, go to step 5.

3.  At this point there are two possibilities:  Either the single "light"
weight is the different one, or the single heavy weight on the side of the
three neutrals is the different one.  Weigh the light one against any
neutral.  If it is the same weight, then the single heavy weight is the
different one.  If it is lighter, then of course it is the different one.
We can stop and report which weight is different.

4.  In this situation, we know that the oddball weight is one of the three
lights which was not involved in the second weighing.  Weigh one of these
against the other.  If they are equal, the third is the oddball; if they
are different, the lighter one is the oddball.  We can stop here.

5.  Here we know that the different weight is one of the three heavies that
were on the same side in the second weighing.  Weigh one of these against
the other.  If they are equal, the remaining heavy is the oddball; if they
are different, the heavier one is the oddball.  We can stop and report
which weight is not identical to the others.

6.  In this step, we know the oddball is among the four weights not used in
step 1.  Call the other eight weights "safe" and call these four "suspicious".
Take two suspicious weights and weigh them against two safe ones.  If the
scales balance, throw away these two suspicious weights and keep the ones
you didn't weigh; if the scales don't balance, throw away the two you
didn't weight and keep the two you did weigh.  Either way, go to step 7.

7.  You are left with two suspicious weights and many safe weights.  Weigh
one suspicious one agianst the safe one; if the scales balance, the
suspicious weight which was weighed is the one you're looking for,
otherwise the suspicious weight which you didn't weigh is the one you
want.
-- 
			Greg Kuperberg
		     harvard!talcott!gjk

"The eerily accurate drawing of Goetz showed the face of the 'before'
figure in comic-book ads for body-building devices."-Time Magazine, April 8