1
$\begingroup$

I understand there are similar problems but I am not sure how to go about constructing this problem with set of balls that are not exponents of 3^n. I know I need at least 2 weighings to find the heavier ball since 3^2 = 9. I was thinking make two groups from the 8 -> two groups of 4 which is in itself contains another subset = { (1)a (3)a } and { (1)b (3)b }.

You weigh the two groups. If one is heavier you can only focus on that. Say group a is heavier. I know there is at least 1 weighings for a set of 3 balls to find the heavier one but what about the (1)a?

$\endgroup$
  • $\begingroup$ Hint: you can find the heaviest ball out of three with one weighing on a balance (work out how). But there are only three outcomes from one weighing (left hand pan goes down, right-hand pan goes down, balance stays level) so you definitely can't do four. $\endgroup$ – Mark Bennet Apr 22 '15 at 21:46
  • $\begingroup$ @MarkBennet: with exactly /one/ weighing operation? I'm puzzled. $\endgroup$ – Tobia Tesan Apr 22 '15 at 22:06
  • 1
    $\begingroup$ @TobiaTesan With balls $ABC$ weigh $AvB$. If the scales go down then either $A$ or $B$ is heaviest (the one which goes down). If the scales stay level, $C$ is heaviest. Applying this to groups of three balls you can do nine in two weighings. You can't do it like this if you don't know whether the different ball is heavier or lighter than the others. $\endgroup$ – Mark Bennet Apr 23 '15 at 5:45
  • $\begingroup$ Duh, stupid me, right. I wasn't thinking of weighing just two balls. Thank you @MarcBennet. $\endgroup$ – Tobia Tesan Apr 23 '15 at 15:30
5
$\begingroup$

Step $I$: Pick $6$ balls and weigh them $3$ on each side.

Step $II$:

$1$. If the balls balance each other, then weigh the remaining two balls and the heavier one will tilt the balance on its side.

$2$. If the balls do not balance each other, then the heavier ball should be one of the three balls on the side the balance tilts. From these three balls, discard one of them and choose the other two to weigh.

  • If the two balls balance each other, then the heavier one is discarded third balls.
  • Else the heavier one will tilt the balance on its side.

EDIT

The idea works in general. At any step given $n$ balls

  • If $n=3k$, divide into three groups of $k$ balls each.
  • If $n=3k+1$, divide into two groups of $k$ balls and one group of $k+1$ balls. Weigh the two groups of $k$ balls and proceed accordingly.
  • If $n=3k+2$, divide into two groups of $k+1$ balls and one group of $k$ balls. Weigh the two groups of $k+1$ balls and proceed accordingly.

Repeat the process at every step.

$\endgroup$
  • $\begingroup$ I understand now. Thank you for providing a clearer picture. I was too focused on dividing the group into (1)a (3)a that I didn't realize that I could just leave the 2 balls out and I would still have a factor of 3 balls on each side to work with. $\endgroup$ – VMO Apr 22 '15 at 21:49
  • $\begingroup$ The key is that you can split it into 3 groups, not 2, so you can distinguish one of $3^n$ balls in $n$ weighings, rather than $2^n$. $\endgroup$ – Neal Apr 22 '15 at 21:55
  • $\begingroup$ I think VMO understood that; the question was how exactly to split it into three groups when the number of balls is not $3^n$. $\endgroup$ – Brian Tung Apr 22 '15 at 21:59
  • $\begingroup$ @BrianTung Yes. I was puzzled if the balls was not 3^n. Say 100 balls for example. I know I need 5 weighings. It is dividing the balls that was not apparent to me intuitively. $\endgroup$ – VMO Apr 22 '15 at 22:07
  • $\begingroup$ What if there are 90 balls and you are not told which one is heavier or lighter? How can we adopt the above strategy to this case? $\endgroup$ – VMO Apr 23 '15 at 21:23

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.