You are given 12 balls that are exactly identical, except for one ball (the faulty ball) having a different weight compared to the others. You do not know whether the faulty ball is heavier or lighter than the rest. Identify the faulty ball using a simple balance only three times.
Solution:
Let us number the balls 1..12
Divide the balls into 3 sets: A={1,2,3,4}, B={5,6,7,8}, and C={9,10,11,12}. We use the notation |S| to denote the weight of balls in set S.
Weighing 1: Use the simple balance with A and B on either side. There are two possible results
Case 1: |A|=|B|
In this case, the faulty ball lies in C
Case1-Weighing 2: Use the simple balance with {9} and {10} on either side
Case 1.1: |{9}|=|{10}|
In this case, the faulty ball is either 11 or 12
Case1.1-Weighing 3: Use the simple balance with {10} and {11} on either side. Remember that 10 is a good ball
Case 1.1.1: |{10}|=|{11}|
In this case, 12 is the faulty ball
Case 1.1.2: |{10}|¹|{11}|
In this case, 11 is the faulty ball
Case 1.2: |{9}|¹|{10}|
In this case, the faulty ball is either 9 or 10
Case1.2-Weighing 3: Use the simple balance with {10} and {11} on either side. Remember that 11 is a good ball
Case 1.2.1: |{10}|=|{11}|
In this case, 9 is the faulty ball
Case 1.2.2: |{10}|¹|{11}|
In this case, 10 is the faulty ball
Case 2: |A|¹|B|
Without loss of generality, let us assume that the set of balls A is lighter than the set of balls B. We can deduce that the faulty ball is in A and it is lighter, or the faulty ball is in B and it is heavier. Let us color code the balls in A (green – light) and B (purple – heavy). Remember that 9 is a good ball. Divide the balls in A and B into three sets as follows: D={1,2,3}, E={4,5,6}, and F={7,8,9}.
Case2-Weighing2: Use the simple balance with E and F on either side
Case 2.1: |E|=|F|
In this case, the faulty ball is either 1, 2 or 3. Remember that if the fault is in this set, then the fault is lighter weight!!
Case2.1-Weighing 3: Use the simple balance with {1} and {2} on either side
Case 2.1.1: |{1}|=|{2}|
In this case, 3 is the faulty ball
Case 2.1.2: |{1}|¹|{2}|
In this case, the lighter of 1 and 2 is the faulty ball
Case 2.2: |E|¹|F|
There are two possible sub-cases here
Case 2.2.1: E is lighter, F is heavier
This can happen only if either 4 is lighter, or 7 or 8 is heavier
Case 2.2.1-Weighing 3: Use the simple balance with {7} and {8} on either side
Case 2.2.1.1: |{7}|=|{8}|
In this case, 4 is the faulty ball
Case 2.2.1.2: |{7}|¹|{8}|
In this case, the heavier of 7 and 8 is the faulty ball
Case 2.2.2: E is heavier, F is lighter
This can happen only if 5 or 6 is heavier
Case 2.2.2-Weighing 3: Use the simple balance with {5} and {9} on either side. Remember that 9 is a good ball
Case 2.2.2.1: |{5}|=|{9}|
In this case, 6 is the faulty ball
Case 2.2.2.2: |{5}|¹|{9}|
In this case, 5 is the faulty ball