From: yao@ee.rochester.edu (Meng Yao)
Newsgroups: soc.culture.china
Subject: answers to a fun problem
Date: 17 Dec 92 00:15:04 GMT
Distribution: usa
Organization: Univ of Rochester, College of Engineering and Applied Science

The first solution of the following was provided by Yiyun Ding which has
already been posted on the net. It's a little confusing to read, but it
is correct. I've also included solutions from joanna@unislc.slc.unisys.com      
and huilong@phoenix.princeton.edu, which are all correct but have minor 
differences. The basic idea is 
to divide the balls into groups of 4 4 5 and make use of good balls.

Solution1:

By Yiyun Ding of Pittsburg

>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.
>  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.
>
>-- 
>//Yijun Ding, Pittsburgh //Go your way, be happy.

Solution2:

joanna@unislc.slc.unisys.com

here is my solution:

Group and label the balls by 4a 4b 5c.  

weight 4a:4b

case 1: = 
	weight 3c:3a (here we know all balls in group a and b are good)
	case 1: = (bad ball is one of 2c left)
		weight 1c : 1a 
		case 1: =
			remaining ball in c is a bad one.
		case 2: <>
			this 1c(weighted) is a bad one.
	case 2: <> (now we know the bad one is heavier or lighter and it
		    is in group 3c)
	           say it is lighter (label L), doesn't matter..so we have 3L
		weight 1L:1L 
		case 1: = 
			remaining ball in L is a bad one.
		case 2: <>
			the lighter one is a bad one according to our assumption

case 2: <> then we know the bad ball is within group a or b. record the group
           as H and L, so we have 4H 4L, we know 5c are all good.
		
	weight 5c : 3H2L
	case 1: =
	        weight 1L:1L(the other 2L left in group L)
		case 1: =  
			the left 1H is a bad one
	        case 2: <>
                        the lighter one is the bad one
	case 2: <> 
		case 1: left side (5c) is heavier
  			then 1H in (5c) is the bad one
		case 2: right side is heavier
		        weight 1H:1H (in right side 3H)
			case 1: = the remaining one in 3H is a bad one
			case 2: <> the heavier one is a bad one.
(done!)

Solution 3:

From huilong@phoenix.princeton.edu 

     step 1.

     put four balls on each side and leave the other five.

A    if the balance is even, the bad ball is in the five unchecked.
     then goto step 2.
     
     step 2.
    
     put three unchecked on one side and three good on the other side.

     if the balance is even then the bad ball must be in the last two
     unchecked, compare one of them with a good one in the step 3, you 
     will get the bad ball.
     or if the balance is not even, say heavy on the side of three unchecked
     ball, you then know the bad ball must be heavier, the step 3 is
     put one from the last three on each side, if the balance is even the
     bad one must be the one left unchecked in the last step, if the balance
     is not even, the one in heavier side must be bad ball. by the same token,
     you can get bad one if it is lighter.

 B   if the balance is not even, the bad one must be in the eight checked.
     then goto step 2.

     step 2.

     take out one from heavier side(A) and two from the lighter side(B), add
     a good one in the lighter side, and exchange one pair from the
     both sides, then see what happens.

     if the balance is even the bad one must be in the three taken out
     in the step 2. the step 3 is comparing the two balls got from the
     lighter side(B) to see which is lighter, that one must be bad one or
     if the balance is even again the one got from the side(A) must be
     bad one.

     if the balance is not even the bad one must be in the five which
     are kept in the balance.

     a. side(A) keeps heavier, the bad one must be in two unexchanged on
        side(A) and one unexchanged on side (B), we got the same case as
        before (see the previous derivation), so we can find the bad one.
     b. side(A) becomes lighter, that means the bad one must be in the
        pair exchanged, so the step 3 is comparing one of them with a good one
        you will get the bad one.