Weight of Heavy Ball - Interview Puzzle


Puzzle DetailsThere are 2187 balls, out of them 1 is heavy. Find the minimum number of attempts the balls have to be weighed for finding out the heavy ball. 


Solution 

First, divide the group of 2187 into 3 groups of 729. Take two arbitrary groups and weigh them. Either they will be imbalanced (in which case you’ve identified the group with the heaviest ball), or they are equal, in which case you know the 3rd group has the heaviest ball.

Now, divide the group of 729 into 3 groups of 243. Take two arbitrary groups and weigh them. Either they will be imbalanced (in which case you’ve identified the group with the heaviest ball), or they are equal, in which case you know the 3rd group has the heaviest ball.

Now, divide the group of 243 into 3 groups of 81. Take two arbitrary groups and weigh them. Either they will be imbalanced (in which case you’ve identified the group with the heaviest ball), or they are equal, in which case you know the 3rd group has the heaviest ball.

Now, divide the group of 81 into 3 groups of 27. Take two arbitrary groups and weigh them. Either they will be imbalanced (in which case you’ve identified the group with the heaviest ball), or they are equal, in which case you know the 3rd group has the heaviest ball. 

Now, divide the group of 27 into 3 groups of 9. Take two arbitrary groups and weigh them. Either they will be imbalanced (in which case you’ve identified the group with the heaviest ball), or they are equal, in which case you know the 3rd group has the heaviest ball.

Now, divide the group of 9 into 3 groups of 3. Take two arbitrary groups and weigh them. Either they will be imbalanced (in which case you’ve identified the group with the heaviest ball), or they are equal, in which case you know the 3rd group has the heaviest ball.

finally, divide the group of 3 into 3 groups of 1. Take two arbitrary groups and weigh them. Either they will be imbalanced (in which case you’ve identified the group with the heaviest ball), or they are equal, in which case you know the 3rd group has the heaviest ball.

You can deduce which one is heaviest at this (7th) step in which 3 balls remaining.


7 times.
in each step we are dividing the number of balls into 3 groups  The number of balls can be represented in base 3 notation and the exponent will become a number of steps involved to find the heavier ball.

2187 = 3^7

hence answer here is 7 steps. a similar approach can be used for larger numbers if it can be represented in base 3 notation.



You may like these posts:

No comments:

Post a Comment