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 ?
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:
Post a Comment