analytical ability and logical reasoning There are $6561$ balls out of which $1$ is heavy. Find the minimum number of times the balls have to be weighed for finding out the heavy ball.
How can I solve this step by step?
 A: Well here's one method.
If you have 3 balls, then weigh two of them. If one of them is heavier than the other, then you've found the heavy one. If they are the same, then the remaining one must be heavy.
This takes 1 weighing.
Now consider $3\times 3 = 9$ balls.
Weigh 3 of them against another 3, leaving 3 to one side. If one group of 3 is heavier than the other group, then the heavy ball must be one of those 3, and the problem reverts to the one above. If the two groups weigh the same, then the heavy ball must be one of the 3 you didn't weigh, and again you know the heavy ball is 1 among 3, and you solve that as above, with one more weighing.
In either case this takes 2 weighings.
Now consider $3\times 3\times 3 = 27$ weights. Break them into 3 groups of nine, and identify the group of nine balls containing the heavy one. This then reduces to the problem above.
This takes 3 weighings.
And we can continue in this way forever.
If you have $3^n$ balls then it will take $n$ weighings to find the correct ball.
And $3^8 = 6561$. So the answer is C.
The only thing is, how do we know there isn't an even more efficient method? Off the top of my head, I can't see a proof that this is the best we can do. Maybe someone else will fill in that detail...
A: The optimality of this method follows, among other things, from information theory: There are 6561 possible positions for the heavy ball, and each weighing gives you exactly three possible informative outcomes: left side is heavier, right side is heavier, both sides are of equal weight. If we write this in terms of entropy, we get
$$ H(1\ weighing) = \log(3). $$
Since the weighings are independent, $n$ weighings have entropy
$$ H(n\ weighings) = n\cdot H(1\ weighing) = n\log(3) = \log(3^n).$$
There are 6561 possible positions for the ball, so
$$ H(position) = \log (6561).$$
The position of the ball completely determines all weighings, hence $H(n\ weighings|position)=0$. What we need is that the n weighings also let us determine the position of the ball, i.e., we want that $H(position|n\ weighings)=0$. But
$$ H(position|n\ weighings) = H(position,n\ weighings) - H(n\ weighings)$$
and
$$ H(position,n\ weighings) = H(n\ weighings|position) + H(position) = H(position). $$
Hence,
$$ H(position|8\ weighings) = H(position) - H(8\ weighings) = \log (6561)-H(n\ weighings)$$
This is exactly zero if $n\ge8$, and greater than zero if $n<8$. It follows that eight weighings are optimal.
(There are some interesting questions remaining about what happens with this information-theoretic explanation if we don't know whether the odd ball is heavier or lighter. I've linked a few interesting blog entries in my blog entry (which is not a good entry on this topic).)
