Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site oddjob.UChicago.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxl!ihnp4!gargoyle!oddjob!matt
From: matt@oddjob.UChicago.UUCP (Matt Crawford)
Newsgroups: net.puzzle
Subject: Re: Coin weighing puzzle *SOLUTION*
Message-ID: <258@oddjob.UChicago.UUCP>
Date: Wed, 30-May-84 16:26:23 EDT
Article-I.D.: oddjob.258
Posted: Wed May 30 16:26:23 1984
Date-Received: Sat, 2-Jun-84 07:29:17 EDT
References: <7280@umcp-cs.UUCP>
Organization: U. Chicago: Astronomy & Astrophysics
Lines: 65

There are 24 cases to distinguish and only 27 possible outcomes of 3
successive 3-valued comparisons, so every test must divide the remaining
solution space up into 3 nearly equal portions.

The first test will split the 24 possible answers into 3 disjoint sets of 8.
The second test will split the 8 into groups of 2, 3, and 3.
The third test must then give the answer.

Call the coins a b c d e f g h i j k l.

compare a+b+c+d : e+f+g+h
		=	then i,j,k,l is heavy or light (8 possibilities)
			compare a+b+c : i+j+k
				      =     then l is heavy or light (2)
				            compare a : l
						      = error
						      > l is light
						      < l is heavy
				      >     then i,j,k is light (3)
					    compare i : j
						      = k is light
						      > j is light
						      < i is light
				      <     then i,j,k is heavy (3)
					    compare i : j
						      = k is heavy
						      > i is heavy
						      < j is heavy
		>	then a,b,c,d is heavy or e,f,g,h is light (8)
			compare a+b+c+e+f : i+j+k+l+d
					  =	then g,h is light (2)
					  	compare g : h
							  = error
							  > h is light
							  < g is light
					  >	then a,b,c is heavy (3)
					  	compare a : b
							  = c is heavy
							  > a is heavy
							  < b is heavy
					  <	then d heavy or e,f light (3)
					  	compare e : f
							  = d is heavy
							  > f is light
							  < e is light
		<	then a,b,c,d is light or e,f,g,h is heavy (8)
			compare a+b+c+e+f : i+j+k+l+d
					  =	then g,h is heavy (2)
					  	compare g : h
							  = error
							  > g is heavy
							  < h is heavy
					  >	then d light or e,f heavy (3)
					  	compare e : f
							  = d is light
							  > e is heavy
							  < f is heavy
					  <	then a,b,c is light (3)
					  	compare a : b
							  = c is light
							  > b is light
							  < a is light
___________________________________________________
Matt			ARPA: crawford@anl-mcs.arpa
Crawford		UUCP: ihnp4!oddjob!matt