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

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