9 balls, 1 defective

You have 9 balls, 8 of which have the same weight. The remaining one is defective and heavier than the rest. You can use a balance scale to compare weights in order to find which is the defective ball. How many measurements do you need so that you will be surely able to do it? What if you have 2000 balls?

First, we put 3 balls on the left side and 3 balls on the right side of the balance scale. If the scale tips to one side, then the defective ball is there. If not, the defective ball is among the remaining 3 balls. Once left with 3 balls only, we put one on each side of the scale. If the scale tips to one side, the defective ball is there. If not, the defective ball is the last remaining one. Clearly we can not find the defective ball with just one measurement, so the answer is 2.

If you had 2000 balls, then you would need 7 measurements. In general, if you have N balls, you would need to make at least log₃(N) tests to find the defective ball. The strategy is the same: keep splitting the group of remaining balls into 3 (as) equal (as possible) subgroups, discarding 2 of these subgroups after a measurement. To see that you need no less than log₃(N) tries, notice that initially there are N possibilities for the defective ball and every measurement can yield 3 outcomes. If every time you get the worst outcome, you will make at least log₃(N) tries.

Published in Insight

We do not know where this puzzle originated from. If you have any information, please let us know via email.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View All Comments