Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site dartvax.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!bellcore!decvax!dartvax!kvetter
From: kvetter@dartvax.UUCP (Keith Vetter)
Newsgroups: net.puzzle
Subject: Re: Weighing problem
Message-ID: <2901@dartvax.UUCP>
Date: Tue, 9-Apr-85 23:37:07 EST
Article-I.D.: dartvax.2901
Posted: Tue Apr  9 23:37:07 1985
Date-Received: Fri, 12-Apr-85 00:00:38 EST
References: <5702@duke.UUCP>
Distribution: net.puzzle
Organization: Dartmouth College, Hanover, NH
Lines: 55

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


*** REPLACE THIS LINE WITH YOUR MESSAGE ***

The problem is commonly stated with 12 coins one of which is 
counterfeit and has the wrong weight.

There are two ways to solve this problem:
  1) use the results of earlier weighings to determine which coins
     to weigh next.
  2) use a set of independent weighings with the coins in such a way 
     to cover all possibilities.  After finishing the weighings, the 
     results are combined to yield the coin.

The second method can be generalized to more than 12 coins but is not 
very appealing (at least to me).

The first method has many cases to keep track of and is as follows:
We'll use the suffix l, h to denote being light or heavy.
1) Weigh coins 1-4 against 5-8.  if they balance then 9-12 contain the bad coin
   2) weigh coins 9, 10 against 11, 1 (a good coin)
      if they balance then 12 is bad
      3) weigh 12 against 1 to see if 12 is heavy or light.

      else we have either 9L, 10L, 11H or 9H, 10H, 11L
      3) weigh 9 against 10
	 if they balance 11 is bad else with 2) we know which is bad.

if the first weighing doesn't balance then assume the pan with coins
1-4 went up (the other case is identical so we'll just solve this case).
Now we know that one of these is true 1L 2L 3L 4L 5H 6H 7H 8H.
   2) weigh 1L, 2L, 5H against 3L, 6H, 9 (good coin)
      if it balances then either 4L, 7H or 8H so
      3) weigh 7H against 8H
	 if they balance then #4 is bad else the heavy one is bad.

      if 2) had the 1, 2, 5 side go down then either 5H or 3L
      3) weigh 5H against 9 (good coin)

      if 2) had the 1, 2, 5 side go up then either 1L, 2L or 6H.
      3) weigh 1L against 2L
	 if they balance then #6 is bad else the light one is bad.

So for 12 coins it takes 12 weighings and you can tell which coin
is bad and whether it's heavy or light.

					Keith Vetter
					Dartmouth College