I recently joined the facebook group “MATH CLUB” (I know, it sounds fun :) ). I was confronted with an interesting (and not quite trivial) problem, known as the “12 ball problem” (or 12 coin problem, whatever).

Anyway, the problem goes like this:

There are 12 balls and all of them weigh the same, except for one (the odd ball) which is slightly heavier or lighter than the other 11. You have a balance scale, which you can use only three times. Can you determine which one is the odd ball, and if it is heavier or lighter than the rest?

After spending a rather large amount of time with this problem, I found a nice solution, which I think is interesting enough to post here. I suggest, reader, that you try to solve this for yourself, before you check the solution. (Good luck!)

Solution:

This is a bit complicated, if you find any mistakes, let me know.

I will use the following notation: “abc / xyz” means that we put a,b and c on one side of the balance and x, y, z on the other. “o” will always denote a ball that we already know not to be odd. “abc > xyz” means that a,b,c together are heavier than x,y,z together. “x+” means that x is the odd ball and is too heavy. “x-” means x is odd and too light.

Divide the 12 balls equally over three sets, so S1 = {e,f,g,h} and S2 = {a,b,c,d} and S3 = {w,x,y,z}. Then we check S1 / S2.

First case: S1 = S2 (so they are equally heavy), then S3 contains the odd ball and S1 and S2 are normal. Check xy / zo. (Choose o from S1 or S2 at random.)

If xy = zo then we know w is odd. Check w / o and we know if w is too light or too heavy.

If xy > zo then we know that x+ OR y+ OR z-. Check x / y. If x = y then we have z is odd-. Otherwise, the heaviest ball between x and y is odd+.

If xy < zo then we do something similar as the xy > zo case.

Second case: S1 > S2 (if S2 < S1, we do something similar), then S1 contains odd+ OR S2 contains odd-. S3 is normal. Check afg / ebo.

If afg = ebo, then we know that h+ OR c- OR d-. Check c / d. If c = d, then h is odd+. Otherwise, the lightest (of c and d) is odd-.

If afg > ebo, then we know that f+ OR g+ OR b-. Check f / g. Etc.

If afg < ebo, then we know that a- OR e+. Check e / o. If e = o, then a is odd-. Otherwise, e = odd+.

In every possible case, we find a solution. Note that we never used more that three balance-checks.

Phew, this was fun :) .