From: chyen@unix386.Convergent.COM (Chien-Hua Yen)
Newsgroups: soc.culture.china
Subject: Re: a fun problem
Date: 23 Dec 92 20:16:41 GMT
Organization: Unisys/Convergent, San Jose, CA

lui@blitzen.cc.bellcore.com (lui,alex) writes:

>In article <BzDMFr.Ayy@news.iastate.edu> zzuo@iastate.edu (Zhiqi Zuo) writes:
>>In article <850@blue.cis.pitt.edu> yding+@pitt.edu (Yijun Ding) writes:
>>>In article <1992Dec16.175720.9520@ee.rochester.edu> yao@ee.rochester.edu (Meng Yao) writes:
>>>
>>>I guess my mail trashed. The answer is bit too complicated to state, but
>>>here goes (just try to be high school kid again):
>>>
>>>put 4 balls on each sides:
>>>if( 4 = 4 )  /* all 8 balls are good balls */
>>>  put 3 from remain ones against 3 good balls
>>>  if( 3 = 3) weigh one of remain two with a good one.
>               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>What if it still balances?  Then, you know the last ball is the bad ball,
>but you don't know whether it's heavier or lighter, and you've used up
>your 3 weights.

>>>  if( xxx > 3 good balls)  /* the bad ball is heavy */
>>>    take 2 from the heavys.
>>>    if( x = x) the remain one is bad, and is heavy
>>>    if( x > x) the heavier is bad
>>>  else if(xxx < 3) ... same
>>>else if(xxxx > oooo)  /* the remain 5 are good, x=heavy o=light */
>>>weigh (xxxoo against the 5 good ball)
>>>if( 5 = 5) /* the question balls are xoo */
>>>  if( xo = 2 good balls) the remain o is bad
>>>  if(xo > 2 good balls) the x is bad
>>>  if(xo < 2...) the o is bad
>>>if( xxxoo > 5 good balls)  /* the bad is in xxx */
>>>  if(x = x)... same as before
>>>if( xxxoo < 5 good balls) /* the bad is in oo */
>>>  ... obvious.
>>>
>>>All except one case, we not only can find the bad ball, but tell if 
>>>it is heavy or light.
>>>

>True, but then it's not a solution now, is it?  If I recall the problem
>correctly, the objective is to identify the bad ball and also determine 
>whether it's heavier or lighter using only 3 weighings.

>>>-- 
>>>//Yijun Ding, Pittsburgh //Go your way, be happy.
>>
>>A Very impressive solution!
>                   ^^^^^^^^

>NOT!  But a good effort nonetheless.  I am pretty sure that this problem as
>it's stated cannot be solved, and that one can prove it using information
>theory (and most likely with other techniques as well).  I remember 
>encountering this problem to prove that it can be done w/ 12 balls but 
>not w/ 13.  Will someone like to present a proof to this? :-)

>-Alex

Here is the solution:

if ( 4 == 4 )  { /* put 4 on each side and balanced */
	the bad ball is one of the untested 5s
	too obvious to solve
} else { /* the bad ball is one of the 8 balls */
	now we have to remember which side is heavier.
	take 2 balls from the heavier side mixed with one ball from the lighter side
	against with 1 balls from the light side mixed with one good ball (any ball
	from the untested 5s) and 1 ball from the heavier side
	if ( 3 == 3) {
		now we know the bad ball is in one of the 3 balls not tested in
		second try which consists of 2 balls in the lighter side and 
		one ball in the heavier side of the first try.
		mix 1 ball from the  heavier side with 1 ball from the light side
		against with 2 good balls
		if ( 2 == 2)
			the 1 ball untestd in the third try is the bad 
			ball
		else
		    if the 2 good balls are heavier,  then the light ball is the bad
			ball otherwise the havier ball is the bad ball.
	} else { /* the bad ball in in one of the 5 balls */
		if (the side with 1 good ball is heavier than othe side) {
			the bad ball must in one of the heavier ball on the side of the
			good ball or the lighter ball in other side.
			test any one of the 2 balls with a good ball
			if (1 == 1)
				the bad ball is the untested one
			else
				the bad ball is the one on scale.
		} else {
			the bad ball must in one of the 2 heavier balls on the othe side
			good ball or the lighter ball on the same side of good ball.
			mix 1 ball from the  heavier side withe 1 ball from the light side
			against with 2 good balls
			if ( 2 == 2)
				the 1 ball in the heavier side untestd in the third try is the 
				bad ball
			else
				if the 2 good balls are heavier,  then the light ball is the bad
				ball otherwise the havier ball is the bad ball.
		}
	}
}

Chien-Hua
Newsgroups: soc.culture.china