1
$\begingroup$
  • 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)
$\endgroup$
  • 2
    $\begingroup$ Check your answer to 2., two weighings suffice (since you know the different ball is heavier). $\endgroup$ – Daniel Fischer Jan 13 '14 at 16:04
  • $\begingroup$ Yes, only 2 weighing are necessary. If you understand why, the third question should be easy to answer as well $\endgroup$ – user127.0.0.1 Jan 13 '14 at 16:06
  • $\begingroup$ 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). $\endgroup$ – fgp Jan 13 '14 at 16:06
  • $\begingroup$ 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. $\endgroup$ – madprob Jan 13 '14 at 16:07
  • 1
    $\begingroup$ @madprob: No, the balance gives (up to) $\log_2 3 \approx 1.585$ bits of information. $\endgroup$ – Henning Makholm Jan 13 '14 at 16:22
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.