Elegant Solution for the Snooker ball Problem

[gautam89]

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

 

[gautam89]

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

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

 

[gautam89]

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)).

Note 3: If A and B are of different weights, put aside p number of balls from the higher weight set, transfer p number of balls from lower weight to higher weight set, and transfer p balls from the set C (of standard weights) to the lower weight set.

Gautam Pandya

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.