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!mercury
From: mercury@ut-ngp.UUCP (Larry E. Baker)
Newsgroups: net.puzzle
Subject: Re: Weighing problem
Message-ID: <1583@ut-ngp.UUCP>
Date: Tue, 9-Apr-85 17:11:57 EST
Article-I.D.: ut-ngp.1583
Posted: Tue Apr  9 17:11:57 1985
Date-Received: Fri, 12-Apr-85 04:45:28 EST
References: <5702@duke.UUCP>
Organization: University of Texas at Austin
Lines: 33

[.]

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

Look in Horowitz & Sahani's "Data Structures" for an excellent
description of using decision trees to solve this sort of problem.  I
don't remember exactly how the solution went, but it went something
like:

Divide the pile into two halves.  Weigh them against each other.  One
will weigh more.  Now halve the two piles, and weigh the halves
against each other.  One pair will weigh exactly the same; this is now
your reference pair.

You can repeat this process (there may be subtitlties not expanded on
here, but it's late in the afternoon, and I have an EE Class in 15
minutes...) but you can repeat this process, eventually coming up with
two items that do not weigh the same.  Select an item from the
reference pair and check each item.  The one that weighs the same as
the item from the refrence pile is NOT the different one.

Note: There may be an easier way to do this (I think there is -- I
have very little faith in my memory) but the above technique should
work.


-- 
-  Larry Baker @ The University of Texas at Austin
-  ... {seismo!ut-sally | decvax!allegra | tektronix!ihnp4}!ut-ngp!mercury
-  ... mercury@ut-ngp.ARPA