12 Balls, 1 Defective

You have 12 balls, 11 of which have the same weight. The remaining one is defective and either heavier or lighter than the rest. You can use a balance scale to compare weights in order to find which is the defective ball and whether it is heavier or lighter. How many measurement do you need so that will be surely able to do it?


SOLUTION

It is easy to see that if we have more than 9 balls, we will need at least 3 measurements in order to find the defective ball (even if we know whether it is lighter or heavier). We will prove that 3 measurements are enough for 12 balls.

We start by placing 4 balls on each side of the scale. Say we place on the left side balls with numbers 1, 2, 3, 4 and on the right side of the scale balls with numbers 5, 6, 7, 8.

CASE 1. The scale does not tip to any side. For the second measurement we place on the left side balls with numbers 1, 2, 3, 9 and on the right side balls with numbers 4, 5, 10, 11.

If the scale again does not tip to any side, then the defective ball is number 12 and we can check whether it is heavier or lighter with our last measurement.

If the scale tips to the left side, then either the defective ball is number 9 and it is heavier or it is number 10/11 and it is lighter. We measure up balls 10 and 11 against each other and if one of them is lighter than the other, then it is the defective one. If they have the same weight, then ball 9 is the defective one.

If the scale tips to the right side, then either the defective ball is number 9 and it is lighter or it is number 10/11 and it is heavier. We measure up balls 10 and 11 against each other and if one of them is heavier than the other, then it is the defective one. If they have the same weight, then ball 9 is the defective one. In all cases, 3 measurements are enough.

CASE 2. Let the scale tip to the left side during the first measurement. This means that either one of the balls 1, 2, 3, 4 is defective and it is heavier, or one of the balls 5, 6, 7, 8 is defective and it is lighter. Clearly, balls 9, 10, 11, 12 are all genuine. Next we place balls 1, 2, 5, 6 on one side and balls 3, 7, 9, 10 on the other side.

If the scale tips to the left, then either one of the balls 1, 2 is defective and it is heavier or ball 8 is defective and lighter. We just measure up balls 1 and 2 against each other and find out which among the three is the defective one.

If the scale tips to the right, then either ball 3 is defective and it is heavier or one of the balls 5, 6 is defective and lighter. We just measure up balls 5 and 6 against each other and find out which among the three is the defective one.

If the scale doesn't tip to any side, then either the defective ball is 4 and it is heavier or the defective ball is 8 and it is lighter. We just measure up balls 1 and 4 against each other and easily find the defective ball. In all cases, 3 measurements are enough.