# Problem Statment

You have 12 balls identical in every way except that one of them weighs slightly less or more. You have a balance scale. Find the Minimum number of comparisons to find the defected ball.

# Solution Approach

Let us number our balls from 1 to 12, so we have {1,2,3,4,5,6,7,8,9,10,11,12}. Divide these balls into three Groups: G1 = {1,2,3,4} G2 = {5,6,7,8} G3 = {9,10,11,12} Weigh G1 and G2, Now Three cases rise,

weight(G1) = weight(G2)
weight(G1) > weight(G2)
weight(G1) < weight(G2)
weight(G1) = weight(G2)

This means the defected ball is in G3

So, suspected balls are {9,10,11,12} and confirmed balls are {1,2,3,4,5,6,7,8}.

Now make two more groups named, G4 = {8,9} and G5 = {10,11} Note: Ball no. 8 is not defected one. Now weigh G4 and G5 and three cases rise,

a) weight(G4) = weight(G5) Our answer is ball 12. b) weight(G4) > weight(G5) Either {9} is heavy or {10,11} is light, so weigh {10} and {11} if both are equal then, ans={9}, else ball with less weight will be answer. c) weight(G4) < weight(G5) Either {9} is light or {10,11} is heavy, so weigh {10} and {11} if both are equal then, ans={9}, else ball with heavy weight will be answer. The Maximum comparison in each case for this scenario is 3.

weight(G1) > weight(G2)

This means either G1 is heavier or G2 is lighter. So, Suspected balls are {1,2,3,4} and {5,6,7,8} and confirmed balls are {9,10,11,12} Now make two groups, G8 = {1,2,5} and G9 = {3,6,9} Now weigh them and three cases arise : a) weight(G8) = weight(G9) So, now suspects balls are {4,7,8} and rest are confirmed balls. Since weight(G1)> weight(G2) so, either {4} is heavy or either of {7,8} is light. Weight ball {7} and ball {8} , if equal answer is ball {4} else answer is ball with lighter weight. b) weight(G8) > weight(G9) So either of {1,2,5} is heavy or {3,6} is lighter. Point to think here: Ball {5} and {3} are no more suspected because, if {5} was heavy then, weight(G2) would have been greater and similarly if {3} has been lighter then also weight(G2) would have been greater. So now we can say either of {1,2} is heavy or {3} is lighter. Weigh ball {1} and ball {2} , if equal answer is ball {3} else answer is ball with heavier weight. c) weight(G8) < weight(G9) So either of {1 , 2 , 5 } is light or {3 , 6 } is heavier. Point to think here: Ball {1,2 } can not be light since the weight of G1 is more and also ball {6} can not be heavy as the weight of G2 is less. So either {5} is lighter or {3} is heavier. Weigh ball {5} with ball {9} , if equal answer is ball {3} else answer is ball {5}. The Maximum comparison in each case for this scenario is 3.

weight(G1) < weight(G2)

This means either G1 is lighter or G2 is heavier. So, Suspected balls are {1,2,3,4} and {5,6,7,8} and confirmed balls are {9,10,11,12}

Now make two groups, G10 = {1, 5 , 6 } and G11 = {2 , 7 , 9} Now weigh them and three cases rise : a) weight(G10) = weight(G11) So, now suspects balls are {3 ,4,8} and rest are confirmed balls. Since weight(G1)<weight(G2) so, either {3 ,4} is lighter or either of {8} is heavy. Weigh ball {3} and ball {4} , if equal answer is ball {8} else answer is ball with lighter weight. b) weight(G10) > weight(G11) So either of {1 , 5 , 6 } is heavy or {2,7} is lighter. Point to think here: Ball {1} and {7} are no more suspected because, if {1} was heavy then, weight(G2) would have been lesser and similarly if {7} has been lighter then also weight(G2) would have been lesser. So now we can say either of {5,6} is heavy or {2} is lighter. Weigh ball {5} and ball {6}, if equal answer is ball {2} else answer is a ball with heavier weight. c ) weight(G10) < weight(G11) So either of {1 , 5 , 6 } is lighter or {2,7} is heavier. Point to think here: Ball {5} and {6} are no more suspected because, if they would have been lighter then weight(G2) would have been less. Similarly, ball {2} is not heavier, as weight(G2) is more. So now we can say either {1} is lighter or {7} is heavier. Weigh ball {1} and ball {9} if equal answer is ball {7} else answer is a ball with heavier weight.

The Maximum comparison in each case for this scenario is 3.