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

1

Solutions for the 13-coin problem are posted at

http://www.creatievepuzzels.com/spel/speel1/speel2/13coin.htm and at

http://www.peacefire.org/staff/bennett/coins.html

I don't think parity is the issue.

EDIT: The question has been edited to require a determination of the weight of the bad ball, relative to the good ones. This can't be done in three weighings; I think the peacefire site I have linked to above settles that. In general, $n$ weighings can find the bad ball, and its relative weight, among $(3^n-3)/2$ or fewer balls.

  • 0
    There is a big difference though: in the 12 coin case, you can determine if the counterfeit is heavier or lighter while finding it. In the 13 coin case, 3 weighings is not enough for this. I do not know a formula for the number of weighings necessary if you don't need to also figure out light/heavy.2012-02-26
  • 0
    I think you can do $(3^n-1)/2$ balls in $n$ weighings if you just want to find the different coin/ball/whatever, and I think a websearch for 12 coin problem or for 13 coin problem will turn up the details.2012-02-27
  • 0
    The answer you pointed cannot tell if the bad ball is heavier or lighter. AFAIK, there is no way to solve 13 balls in 3 weighings.2012-02-27
  • 0
    The question as you stated it asked to identify the bad ball; it did not ask to further determine the relative weight of the bad ball. So the links do solve the 13 ball problem **as you stated it** in 3 weighings. You are correct that there is no way to solve the problem you didn't ask, the one where you also have to decide the relative weight of the bad ball, in 3 weighings.2012-02-27
  • 0
    @GerryMyerson: Perhaps you are right. I remember reading about this in the USSR Problem book, and IIRC, they gave the formula for the "12 ball" case [$(3^n-3)/2$], but they did not state the corresponding formula for the harder "13 ball" case.2012-02-27