Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Dupe? math.stackexchange.com/questions/15423/… –  Aryabhata Feb 26 '12 at 20:12
    
@Aryabhata The context is essentially the same, though the question is still different in the angle. –  pegausbupt Feb 26 '12 at 20:18

1 Answer 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.

share|improve this answer
    
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. –  user641 Feb 26 '12 at 23:45
    
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. –  Gerry Myerson Feb 27 '12 at 0:29
    
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. –  pegausbupt Feb 27 '12 at 4:33
    
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. –  Gerry Myerson Feb 27 '12 at 4:53
    
@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. –  user641 Feb 27 '12 at 6:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.