• The Twelve Balls Problem

    Alex Tabarrok proposed a problem similar to one proposed to me in college. You can read his problem on his blog. Below I state mine, which you can also find elsewhere on the internet. I kept my notes on how to solve it which I also include below (don’t peek if you want to try to solve the problem on your own).

    Problem: There are 12 balls, one of which is a different weight than the other equally-weighted eleven balls. Using a pan balance three times find the anomalous ball and also whether it is heavier or lighter than each of the others.

    There are no tricks or gimmicks. This is an honest problem. It can be solved. Below is my solution. I think (hope) my notation is self-explanatory.

    Solution: (Click to enlarge photos. If it is still too small use the magnifying glass icon in the upper right on the referred page.)

    balls 001

    balls 002

    • That’s funny… i got asked a variation on an interview once. I took it one step deeper and tried to argue a slightly better algorithm depending on expected vs. worse case =)

    • I was asked to do this same thing with 36 balls during an interview. Again, 3 weighs and must tell which one is the odd one out (heavier or lighter).

      Solution was similar (see your own solution for details)

    • I did not understand your solution, maybe I haven’t looked hard at understanding it. I think I can solve it like this. Split 12 in groups of 4. Compare first 4 with the other 4. If you get a difference take those 4, and then do 2 against two and finally a one against one. If 4 v 4 turns out same directly take the remaining 4 and repeat 2v2 and 1v1.