Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Elegant Solution for the Snooker ball Problem

  1. Jun 27, 2010 #1
    Snooker balls Problems – An Approach to Elegant Solutions:

    Problem Definition: In a set S of snooker balls, all of the same standard weight, there is one ball of non-standard weight.

    Using a Scale Balance, find the non-standard ball with minimum number of trials- Provide a formula and a proof.
    Proposition 1. Set S contains One non-standard ball of known relative weight -Identify non-standard :
    Solution: For Quantity = 3 (to power n), or less;
    Min weighing required = n.
    Proposition 2: Set S contains One non-standard ball- of unknown relative weight; find the ball and identify its relative (heavier or lighter) weight ?:
    Solution: For Qty = ( 3(power n) + 3(n-1) + 3 (n-2) … 3(2) + 3(1) ) or less;
    Min weighing required = n +1.
    An approach to proofs of solutions:

    Definition 1: (Ternary partition)
    Divide the set S into three subsets A, B, and C, where
    1. Qty(S) = Qt(A)+Qty(B) +Qty(C), and
    2. Qty(A) = Qty(B) >= 1/3 x Qty(S), and
    3. Qty(C) = Qty(A) - i; where i = 0,1 or 2.

    Proof For Proposition 1: Weigh A with B. This will identify which of the subsets A, B, or C has the non-standard (with known relative weight) ball. – Recursively use n-1 weighings to find the non-standard ball (of known relative weight).

    Definition 2 : (“Weight type”)
    1. A ball is of “ heavier weight type” when it can NOT be lighter ball.
    2. A ball is of “ lighter weight type” when it can NOT be heavier ball.
    3. A subset of balls is called of a specific “weight type” if all the balls in that subset is of that “weight type”

    Proof For proposition 2:
    1. Divide the set S into its Ternary subsets A, B, C (Definition 1), and weigh set A & B.
    2. If A and B are Not equal, then using the “weight type” concept and Proposition 1, one can “cross-weigh” subsets of A, B and C n times, to find the non-standard ball from A or B, and identify if it is heavier or lighter ball
    3. If subsets A and B are equal then the non-standard ball is in C, and again one can use “cross weighings” and Proposition 1, n times to find and identify the relative weight of the non-standard ball in subset C.

    What about problem when there are TWO non-standard balls (of equal weights)...

    Gautam Pandya
  2. jcsd
  3. Dec 26, 2010 #2
    Notes on Elegant Proof of Snooker Ball problem
    Note 1: Exceptions to the Ternary partitions:
    For Qty(S) = 7, Ternary partition is 7 = 2 + 2 + 3
    For Qty(S) = 10. Ternary partistion is 10 = 3 + 3 + 4

    Note 2: let p = MIN ((3(power n-1), Qty(C)). Cross weighing p balls from sets A, B and C, and using Proposition 1, One can easily prove proposition 2.
    Gautam Pandya
    Last edited by a moderator: Dec 26, 2010
  4. Dec 27, 2010 #3
    Note 4: Weigh the modified sets A and B. If they weigh opposite to their earlier weight types then the non-standard ball must be one of the p balls transferred from the lower weight type. If modified sets are equal then the non-standard ball is one of the p balls put aside from the higher weight type. In these two cases, Recurssively one can find the non-standard ball and identify its weight type.

    Note 5: If modified sets weigh the same way as the original sets A and B, then non-standard ball is amongs the "remaining" balls in A and B. In this case, take
    p = 3(power n-2), and repeat steps in Notes 3 and 4 above, and recurssively prove the proposition 2.
    Note 6: If A = B the repeat steps then A and B has all standard balls and repeat steps in Note 3 and 4 above for Set C.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook