The ole 12 snooker ball question (and my job)

[seadalton]

Hello,

There is a similar thread in brain teaser's, but I can't seem to find it. So let me first apoligize for the lack of net ettiquette.

I had an interview today with the ole snookerball and scale question. First it was 8 balls, 7 of equal weight and 1 of an odd weight (could be heavier could be lighter) and I was asked to find the minimum number of measurements (turns out to be 2. Then the interviewer kicked up the heat and ask the same riddle if I had 12 balls, 11 of equal weight etc etc. WIth 12 balls the answer is 3 measurements.

So far so good. To really stump me I was then asked for a formula to determine how many measurements it would take for X Set where X number of balls where all equal weight and one ball was of an unequal weight (again could be heavier or lighter).

Dispite sweating bullets at the whiteboard I gave a weak answer of x/4 because that works for both 8 balls and 12 balls. Apparently it doesn't work for 24 balls becuase the heavy ball could be identified with 4 measurements if I had 24 balls.

Soooooooo, not being a math genius, I hope someone smatter than me (my second guess was that I could find the answer on google) can offer an algorithem to determine the minimum number of measurements it would take to distingues the odd balls of any set of balls where only 1 is of a different wieght, again, could be heavier could be lighter.

Thanks for your time.

Cheers

 

[neurocomp2003]

shouldn't the 24 be determined in only 3 moves? any ways i see the pattern
upto 3-1 turn
upto 9-2 turns
upto 27-3 turns
so the formula would be something like
let k be the number of moves.
let n be the number of balls
smallest k: n<3^k;

 

[gerben]

upto 3-1 turn
upto 9-2 turns

How would you do this?
(you do not know whether the oddball is lighter or heavier)

 

[chronon]

From http://www.cut-the-knot.org/blue/OddballProblem1.shtml it looks to be log₃ (2N+3) (rounded up to the next integer). But you can also do it in log₂N weighings (again rounded up) -which will be smaller for small N. However, both of these give 3 weighings for 8 balls, and I'm not convinced that you can do it in 2 - can you explain?

 

[seadalton]

chronon, et all, thank you for the input so far.

Here is how I worked out 2 weighings for 8 balls
start with 8 balls
First weighing is 123 vs 456 (balls 7 & 8 are set aside)
Lets say I get lucky and 123 vs 456 balance each other.
That means either 7 or 8 is the odd ball so my second weighing compares the two and the scale tips to the heavier (at least for my interview quiz it didn't matter if the odd ball was heiver or lighter so I just chose heavier).

Lets say I'm not so lucky with the 7 and 8 ball.
1st weighting: I start again with the 123 vs 456 on the scale, 7 & 8 are set aside. 456 is the heavier set but I know that 1,2,3,7 & 8 are all equal.
2nd weighing 4 vs 5 and 6 is set aside.
The second weighing can have 3 outcomes
1- the scale towards ball 4 and that is my heavy ball
2- the scale tips towards ball 5 and that is my heavy ball
3- the scale is blance so 4 and 5 are of equal weight which leaves only ball 6 as one having an unequal weight when compared to the others in the set.

So, I probably wasn't clear with my original posting. For my interview, I didn't have to determine if the odd ball was heavier or lighter, just that it was an odd ball.

Again to all, thanks for your input(s) and if you have other ideas or formula's I'm all ears, umm all eyes.

Cheers

 

[chronon]

If you know that one ball is heavier then its log₃N, as implied by neurocomp2003. But in this case you can do 24 balls in 3 weighings.

 

[LarrrSDonald]

That means either 7 or 8 is the odd ball so my second weighing compares the two and the scale tips to the heavier (at least for my interview quiz it didn't matter if the odd ball was heiver or lighter so I just chose heavier).

I don't get it.. That wouldn't identify the odd ball would it? If, for instance, 7 is light and 8 is normal, then you'd be picking 8 as the odd ball while in fact it's the same as all the others except 7. You'd only know that either 7 is light or 8 is heavy, not which one is unusual compared to the others (nor if the odd one is heavy or light, but that wasn't the question). The same problem ought to apply to the 1 vs 3 or 4 vs 6, unless you get a balance either could be the odd ball.

 

[seadalton]

Larrrs, Thank you for posting.

The evil pointed head interviewer put the question to me that all balls were the same, except one, which was heavier than the rest of the population.

Cheers

 

[chronon]

From http://www.cut-the-knot.org/blue/OddballProblem1.shtml it looks to be log₃ (2N+3) (rounded up to the next integer). But you can also do it in log₂N weighings (again rounded up) -which will be smaller for small N. However, both of these give 3 weighings for 8 balls, and I'm not convinced that you can do it in 2 - can you explain?

The case N=4 (when you don't know whether the extra ball is light or heavy) has been bothering me as its the only case where ceil(log₃ (2N+3) )>ceil(log₂N). I think that the formula should actually be ceil(log₃ (2N+1)), and this is the best you can do. (n.b. for N=2 the problem is insoluble)

 

[gautam89]

Snookerball Problems - Solution:

1.one non-standard – but of known relative weight -Identify non-standard :
Solution: Quantity = 3 (to power n), or less; Trials=n.

2.One non-standard- unknown relative weight; find and identify relative weight ?:

Solution: Qty = ( 3(power n) + 3(n-1) + 3 (n-2) …… 3(2) + 3(1) ) or less; Trials = n +1.

Gautam Pandya
---------------------