Measurements – Puzzle Prime

A common type of brain teasers asked at Quant Interviews is Measurements. The simplest example is the problem:

Problem: You have scales and 9 balls, one of which is heavier than the others. How many measurements do you need in order to find the heavier ball?

SOLUTION

You need only 2 measurements. First, place 3 balls on one side of the scales and 3 balls on the other side. If the scales are not balanced, then the heavier ball will be among the heavier group of balls. If the scales are balanced, the heavier ball will be among the remaining 3 balls. Next, measure 2 of the balls in the heavy group against each other, and figure out if any of them is heavier, or the heavier ball is the remaining third one.

This problem can be generalized to any number of balls. Clearly, with the strategy above, with N measurements, we can find the heavier ball in a set of up to 3ᴺ balls. As it turns out, this bound is sharp, e.g. you can not find the heavier ball in a set of 30 balls with just 3 measurements.

The reason is that every measurement can have 3 outcomes, left side heavier, right side heavier, or both sides equally heavy. Therefore, if we are unfortunate, it is possible that every measurement takes out at most 2/3 of the remaining possibilities. If we start with 30 balls, one of which is defective, then the number of possibilities initially is 30. After the first measurement, it is possible that we end up with 10 possibilities. After the second measurement, it is possible that we end up with 4 possibilities. After the third measurement, it is possible that we end up with 2 possibilities and can not conclude which the defective ball is.

This principle can be used to help us guess the answer of such Measurement problems and guide us through figuring out the solution.

Problem: You have scales and 12 balls one of which is either heavier or lighter than the rest. How many measurements do you need in order to find the defective ball?

SOLUTION

First, we note that there are 24 total possibilities for the set of balls: 12 due to the number of balls, and 2 due to the fact that we do not know whether the defective ball is heavier or lighter. Since every measurement with the scales can have 3 outcomes, we conclude that we need at least 3 measurements. With 4 measurements, we can generally filter 1 out of up to 64 possibilities, so our best guess would be that the answer is 3.

We can see that our optimal choice for the first measurement would be to place 4 balls on each side. That way, if say, the left side is heavier, we would have 8 possibilities remaining: the defective ball is heavier and it belongs to the left group, or the defective ball is lighter and it belongs to the right group. If the two sides are equally heavy, then the defective ball will belong to the remaining group of 4 balls and it will be either heavier or lighter.

Puzzle Newsletter