strategy - Twelve balls and a scale

You are given twelve identical-looking balls and a two-sided scale. One of the balls is of a different weight, although you don't know whether it's lighter or heavier. How can you use just three weighings of the scale to determine not only what the different ball is, but also whether it's lighter or heavier?

Answer

Split this into three groups of four, A1, A2, A3, A4; B1, B2...; C1, C2... Each step here corresponds to one weighing.

• Weigh A against B.
  
  
  
  
  • If A > B, then weigh A1, B1, and B2 against B3, B4, and C1.
    
    
    
    • If the weights are equal, then one of A2...4 is heavier; weigh A2 and A3. If they are equal, A4 is heavier. If one is heavier, then that ball is heaviest.
    
    
    • If the first group is heavier, then either A1 is heavier, or B3-4 is lighter. Compare B3 and B4; if they are equal, A1 is heavier; if they are different, the lightest is the lightest ball.
    
    
    • If the first group is lighter, then either B1 or B2 is lighter. Weigh them and see.
    
    
    
    
  
  
  • If A < B, renumber all A-balls to B-balls, and perform the above steps.
  
  
  • If A = B, weigh A1, A2, A3 against C1, C2, C3
    
    
    
    
    • If they are equal, then weigh A1 against C4. If A1 is lighter, then C4 is the odd ball and it is heavy. If A1 is heavier, then C4 is the odd ball and it is light.
    
    
    • If A is heavier than C, weigh C1 against C2. If they are equal, then C3 is the odd ball and it is lighter. If they are not equal, then the lighter of the two balls is the lightest ball
    
    
    • If A is lighter than C, weigh C1 against C2. If they are equal, then C3 is the odd ball and it is heavier. If they are not equal, then the heavier of the two balls is the heaviest ball.
    
    
    
    
  
  
  
  

We can work backwards from the third step to see, approximately, why this works. At the third weighing, the options need to be reduced to either two or three balls. This means that the second weighing must reduce to either two or three possible balls.

We know that the first step will remove either 1/3 or 2/3 of the possible solutions, no matter what you do. This means that, in the 1/3 case, you need to split the possibilities down from 8 into a group of 3, a group of 3, and a group of 2. From this, the third weighing points to the odd ball out. Because this case implies one set of balls is heavier, by virtue of finding the odd ball out, we know whether it's heavier or lighter, so we actually don't need to worry about this piece of information at all.

In the 2/3 case, you need to reduce the possibilities into a group of 3 and a group of 1, which is easy enough to do intuitively. Because we actually don't know the relative weight of the odd ball in this case, the information from the third weighing must be used to determine whether the ball is heavier or lighter.