13 Balls Problem

Problem

You have 13 balls identical in size and appearance but 1 is an odd weight (could be either lighter or heavier). 

You have a balance to compare the weights on the two sides. 

You have only 3 chances to weigh the balls in any combination using the balance. Determine which ball is the odd one and if it's heavier or lighter than the rest. How do you do it? There is an exception in the problem. Find that as well.

Solution

Divide the balls into 3 groups having 4 balls each and one loner
A1, A2, A3, A4
B1, B2, B3, B4
C1, C2, C3, C4
D1

Comparison 1
compare(A1+A2+A3+A4 in left and B1+B2+B3+B4 in right)

If they don't balance, name the side which is heavier as A1, A2, A3, A4 and the side which is lighter as B1, B2, B3, B4

           Comparision 2
           compare(A1+A2+C1 and A3+A4+B1)

           If left is heavier means either A1 or A2 is the heavier ball or B1 is the lighter ball

                      Comparison 3
                      compare(A1 and A2)
                      If they balance then B1 is the odd ball and lighter
                      Else the heavier of A1 and A2 is the odd ball and heavier

           If right is heavier means A3 or A4 is the heavier ball

                      Comparison 3
                      compare(A3 and A4)
                      The heavier of A3 and A4 is the odd ball and heavier

           If they balance means either of B2, B3, B4 is odd ball and lighter

                      Comparison 3
                      compare(B2 and B3)
                      If they balance then B4 is the odd ball and lighter
                      Else the lighter of B2 and B3 is the odd ball and lighter

If they balance means the odd weight is among C1, C2, C3, C4 or D1

           Comparison 2
           compare(A1+A2+A3 and C1+C2+C3)

           If left is heavier means either of C1, C2, C3 is lighter

                      Comparison 3
                      compare(C1 and C2) 
                      If they balance means C3 is the odd ball and lighter
                      Else the one which is lighter of C1 and C2 is odd ball and lighter

           If right is heavier means either of C1, C2, C3 is heavier

                      Comparison 3
                      compare(C1 and C2)
                      If they balance means C3 is the odd ball and heavier
                      Else the one which is heavier of C1 and C2 is odd ball and heavier

           If they balance means C4 or D1 is the odd ball

                      Comparison 3
                      compare(A1 and C4)
                      If they don't balance means C4 is the odd ball and heavier or lighter

                      Else D1 is the odd ball (Exception: we can't find whether it is heavier or lighter in 3 comparisons)


Explanation for Exception
13 Balls Problem is exactly like 12 Balls Problem.

In 12 Balls Problem, if C4 is odd, we know after comparison 2 that C4 is odd. But compare it just to know whether it is lighter or heavier. We know its not going to balance. 
In 13 Balls problem, C4 can balance if D1 is odd. But if it balance, we don't know whether D1 is heavier or lighter because D1 was never on the balance in the 3 comparisons. For this case (1/13th probability), we would require 1 more comparison to find whether D1 is heavier or lighter.

If the problem is minimum number of comparisons just for finding the odd ball, the answer is 3 comparisons.
But if the problem is minimum number of comparisons for finding the odd ball and also whether it is heavier or lighter, answer will be 4 comparisons.