Monday, July 23, 2012

8 balls problem and solution


Given 8 identical balls, there is a fake ball, which may be either heavier or lighter. Assume that there is a balancing-scale available.
To identify the fake ball,
1.) how many rounds of comparisons are needed?
2.) how many rounds of comparisons are required if the number of balls is n?

Solution 
A useful definition :
A control ball : A ball that did not cause the scale to tip. Since we know that there is only one ball that is different  select a control ball intuitively form the n-1 possible ones.

1.) 3 weighings.
Number the balls 1-8
  • Weigh 1-2 / 3-4 Three outcomes: 
    • 1-2 is lighter : Weigh 1 / 2 . Three outcomes: 
      • 1 is lighter. Yup then 1 IS lighter 
      • 2 is lighter. Yup then 2 IS lighter
      • Equal. Well weigh 3 / 4 and one is bound to be heavier :) 
    • 3-4 is lighter : proceed same as 1-2 is lighter. 
    • Equal - Weigh 5-6 Three outcomes: 
      • 5 is lighter : Weigh against a control ball (any from 1-4). If same 6 is heavy otherwise 5 is light. 
      • 6 is lighter : same as 5 is lighter 
      • WORST CASE equal: Weigh 7 and a control ball (any from 1-4). Answer should be evident. 
2.)
Since in each step you split your sample space in half.  So in general you need log(n,base2) steps. 

Further analysis
If you know whether the ball is heavier OR lighter the weighings reduce to log(n) -1. Also if you need to know whether the fake ball was heavy or light (not just identify the ball). You will need one more weighing, in case 7 was not fake, you would know 8 is fake but not if its heavy or light.

Bad approach
The first intuition is to try and weigh 4 balls / 4 balls instead of 2 balls / 2 balls shown here. The problem with 4/4 approach is that you do not know which particular set of balls have a problem. You only find the direction of the problem for a set of 4 balls. You need to focus on discriminating the balls and that will intuitively lead you to a classification of 2 / 2 balls initially which tells you WHICH 4 balls have the problem.