Recently, my lab mate Patrick came to my office and proposed to give the following question for an exam in information theory: Explain why exactly two weightings on a standard balance scale suffice to determine which out of nine balls is heavier than the other eight (which have all the same weight).
Everybody knows the puzzle, and most know the solution: Split the nine balls in groups of three and weigh them. The heavier triple must contain the heavy ball, so you can weigh two balls of the heavier triple. If they balance, the third ball must be the heavy one. Similarly, if the first two triples have the same weight, the heavy ball must be in the third triple that you did not weigh in the first step.
In fact, it turns out that in this case two weightings are not only the minimal number of weightings necessary, but also the optimal number: Each weighting gives us three results (right heavy, left heavy, balanced), so two weightings give us nine results. And, there are exactly nine balls, one of which we have to determine. Hence, if we want to put it in terms of information theory, the number of bits needed to encode the position of the heavy ball is equal to the number of bits obtained from the scale in two weightings:
$$ H(balls) = \log 9 = 2 \log 3 = 2 H(scale) $$
Things get a bit more difficult if we do not know whether the odd ball is heavier or lighter than the rest. Assume that the ball is in one of the first two triples which we weigh. Then, the scale does not immediately tell us in which of these triples it is: If the odd ball is lighter, then it is in the triple going up, if the odd ball is heavier it is in the triple going down. But there is a very nice scheme which allows us to determine the position of the odd ball and whether it is heavier or lighter in three weightings. And again, information theory tells us how to interpret this. Given that there are two possibilities for the weight, $H(weight)=\log 2$, we have
$$ H(balls,weight) = \log 9 + \log 2 = \log 18 < \log 27 = 3\log 3 = 3H(scale) $$
So, three weightings give us more than enough information about whether the odd ball is heavier or lighter, and where it is. I don't want to reproduce the algorithm to find the odd ball here, just let me tell you that three weightings are sufficient for more than nine balls, too. We only have to guarantee that $H(balls,weight)\le 3H(scale)$. The solution to find the odd ball out of twelve is given in the Wikipedia article about the Twelve-Coin-Problem.
It turns out that if we are not interested in the weight of the odd ball, but just in its position, an ordinary balance scale might not be the right type of measurement device. Although thirteen balls would still satisfy above equation, giving
$$ H(balls,weight) = \log 26 < \log 27 = 3H(scale) $$
three weightings tell us the odd ball, but not whether it is heavier or lighter (see Manish's comment to this blog entry or this website). But why is that so? Raj on Quora wrote that with $n$ weightings you can find the odd one of at most $(3^n-1)/2$ balls and the odd one and its weight from at most $(3^n-3)/2$ balls. For $n=3$ this evaluates to 12 and 13, respectively, so the result seems to be correct.
Still, I'm not totally happy with it. If it's true, then there should be a sequence of results expressing this also in terms of entropy, or in terms of conditional entropy of, say, the position given the results of the first two weightings. There is some work to do to improve intuition about this problem, although Raj already did a very good job. Let me know when you're done!