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?

  • 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
    @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