The ole 12 snooker ball question (and my job!)

  • Thread starter seadalton
  • Start date
4
0

Main Question or Discussion Point

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
 

Answers and Replies

1,349
2
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;
 
508
1
neurocomp2003 said:
upto 3-1 turn
upto 9-2 turns
How would you do this?
(you do not know whether the oddball is lighter or heavier)
 
488
0
From http://www.cut-the-knot.org/blue/OddballProblem1.shtml it looks to be log3 (2N+3) (rounded up to the next integer). But you can also do it in log2N 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?
 
4
0
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
 
488
0
If you know that one ball is heavier then its log3N, as implied by neurocomp2003. But in this case you can do 24 balls in 3 weighings.
 
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.
 
4
0
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
 
488
0
chronon said:
From http://www.cut-the-knot.org/blue/OddballProblem1.shtml it looks to be log3 (2N+3) (rounded up to the next integer). But you can also do it in log2N 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(log3 (2N+3) )>ceil(log2N). I think that the formula should actually be ceil(log3 (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
---------------------
 
Last edited by a moderator:

Related Threads for: The ole 12 snooker ball question (and my job!)

  • Last Post
2
Replies
25
Views
9K
  • Last Post
Replies
15
Views
7K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
22
Views
3K
  • Last Post
2
Replies
40
Views
5K
Replies
10
Views
2K
  • Last Post
Replies
3
Views
679
Top