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$
4
  • $\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$ Apr 22, 2015 at 21:46
  • $\begingroup$ @MarkBennet: with exactly /one/ weighing operation? I'm puzzled. $\endgroup$ Apr 22, 2015 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$ Apr 23, 2015 at 5:45
  • $\begingroup$ Duh, stupid me, right. I wasn't thinking of weighing just two balls. Thank you @MarcBennet. $\endgroup$ Apr 23, 2015 at 15:30

1 Answer 1

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$
5
  • $\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$
    – AG10
    Apr 22, 2015 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, 2015 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, 2015 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$
    – AG10
    Apr 22, 2015 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$
    – AG10
    Apr 23, 2015 at 21:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .