# How many times do we need to weight to find the only heavy ball out of $3^n$ balls?

• There are three identical balls of which two are of same weight and one is heavier. A balance instrument is given. How many minimal times one needs to measure to find out the heavier ball? (This is easy, just 1 time)
• What will be the answer of the problem for nine identical balls of which one is heavier? (2 times)
• The general question: What will be the answer for $3^n$ balls of which one is heavier? (I could not calculate this)
• Check your answer to 2., two weighings suffice (since you know the different ball is heavier). – Daniel Fischer Jan 13 '14 at 16:04
• Yes, only 2 weighing are necessary. If you understand why, the third question should be easy to answer as well – user127.0.0.1 Jan 13 '14 at 16:06
• A lower bound is $n$ measurements for $3^n$ balls - with $n$ measurements you can distinguish $3^n$ cases, since each measurements can produce three possible results (left side heavier, right side heavier, both the same). – fgp Jan 13 '14 at 16:06
• Since the balance gives you $1.5$bit of information. It follows straight from information theory that, for $3^{n}$ balls you need at least $n$ measures. Now find the strategy with $n$ measures. – madprob Jan 13 '14 at 16:07
• @madprob: No, the balance gives (up to) $\log_2 3 \approx 1.585$ bits of information. – Henning Makholm Jan 13 '14 at 16:22

With $3^{n+1}$ balls, $n\ge 0$ pick $3^{n}$ balls for the left scale and $3^{n}$ for the right scale (and ignore the remaining $3^{n}$ balls for the moment. If the left scale goes down, you know that the heavy ball is among the left $3^n$ balls; if the right scale goes down, you know the heavy ball is among the right $3^n$ balls; and if the balance is equal, you know that the heavy ball is among the $3^n$ ignored balls. At any rate, you have managed to reduce the problem with a single weighing to finding one heavy ball among $3^n$ balls. By repeating this step (i.e. essentially by induction) we see that it $n$ weighings are sufficient for $3^n$ balls.
For $3^2$ identical balls, you first divide the balls in 3 groups of $3^1$ balls to find the one which contains the heavier ball. And with $3^1$ balls, you just have to measure once. So 2 measurements.
For $3^n$, you divide the balls in 3 groups of $3^{n-1}$ balls and discover the group which contains the heavier ball. Repeat this procedure $n-1$ times and you'll get your ball.