Saturday, October 13, 2012

Find the Defective ball.

Here's a very well known puzzle.

You are given 9 balls of equal size, color and texture. one of them is defects. All balls have the same weight, except the defective one which has a higher weight.  Lets say you are given a simple balance for measurement,  How many measurements would you need to find out the defective one ?
..
.
.
.
.
.
.
.
.
.
.

Solution :-

Most people either come up with the answer as 3 or 4. But the answer is two. The trick is to do elimination. In this case, from the 9 balls 6 of them can be eliminated by dividing 9 balls into 3 sets of 3 balls each. Lets call them Set A, Set B and Set C.

Place A on one side of the simple balance and B on the other side of balance and measure. If they measure equally, then the defective (overweight) ball is on the third set C. If A weighs more than B, (then the weight of B & C will be equal), the defective (overweight) ball is in Set A, whereas if B weighs more than A, then its in Set B. In a single measurement, we could eliminate 6 out of 9 balls and narrow down the search to 3 balls.

Now, lets call three balls x,y,z. Measure x against y in the simple balance.

if x = y then z is the defective ball
if x > y then x is the defective ball
if y > x then y is the defective one.

So, the answer is 2 measurements.

Variation : For the same 9 balls and 1 defective ball problem, lets say the defective ball has a different weight, but we do not know whether its overweight or underweight. Whats the least number of measurements then ? 

No comments: