2
$\begingroup$

As many of you might have seen before, here is the description of the classic weighing balls problem:

One of twelve pool balls is a bit lighter or heavier (you do not know) than the others. At least how many times do you have to use an old balance-type pair of scales to identify
this ball and tell if it is heavier or lighter?

I know the answer is $3$, which is the lower bound given by the information theory since $\lceil\log_3(2\cdot12)\rceil=3$. Now my question is: can the answer still remain be $3$ if the number of balls is $13$ rather than $12$ (since $\lceil\log_3(2\cdot13)\rceil=3$ as well)? More general, how does the parity of the number of balls here affects the answer in our weighing ball context?

  • 1
    Dupe? http://math.stackexchange.com/questions/15423/optimal-algorithm-for-finding-the-odd-spheres2012-02-26
  • 0
    @Aryabhata The context is essentially the same, though the question is still different in the angle.2012-02-26

1 Answers 1