12 Ball Probelm

Dear Internet,

I'm a little disappointed in you.  I recently got hooked by the 12 ball problem (defined shortly), and while I found some solutions and discussion, you left me without a satisfying solution: one that really got to the meat of the issue and explained what's going on.

Here's a statement of the 12 ball problem.  You are given 12 balls, 12 identical except one weighs slightly more or slightly less than the others.  Your task is to discover the oddball and report if it's heavier or lighter.  You are given a balance scale which is the only instrument you may use to make this judgement, and you may have no more than three weighings of groups of balls (choose any number on each side of the balance) against each other to determine which of the 12 is different, and whether it's lighter or heavier.  Moreover, you must determine which balls are to be weighed against each other ahead of time - it is illegal to make your weighing schedule contingent on previous results.

There are a few solutions out there, and you can look them up.  Here's one.  However, I couldn't find a satisfying treatment of the approach used to solve this problem, so I'm offering one to you, O Mighty Internet, right here, right now.  (OK, far below this text so I don't spoil anything.)  Give it a shot, if you like.  It took a satisfying 15 minutes or so for me, including one 2-minute stroll.  Hint: start with a principled approach; trial-and-error will take a long time.






















Is your screen this tall?  Yes?  OK, I'll add more whitespace.























OK.  That should do it.  Here are the facts to get you started.  There are 24 possible problem states, and you have 3 observations per weighing.  Each weighing can have the scale tip left, tip right, or stay steady: 3 states.  Therefore, there are 3*3*3=27 possible observations, mapping onto 24 states you have to distinguish.  That's pretty tight, and given a fixed schedule of what balls to weigh when, you're going to need to ensure each outcome is about equally likely, or you simply won't have enough information to disambiguate the 24 possibilities.  Scroll down for the next hint.




























To make each possibility approximately equally likely, you're going to need to weigh the balls 4 against 4, reserving 4 for later.  Then the chances of a left, right or steady observation are equal on each round.  Scroll for more...






















Since you don't know if the oddball is heavier or lighter than the others, you can't have any patterns where, say, ball 2 being heavy would tip the scales R(ight) L C while a heavy 4 tips them L R C, since a light 4 would be indistinguishable from a heavy 2.




















That means there need to be 4 similar groups of 3 balls, each of which would tip the scales in an idiosyncratic way.  Group I would cause tips in all three rounds, twice in one direction and one in the other direction.  Group II causes tips in the same direction in two of the three rounds, and an even weighing on the third.  Group III causes tips in opposite directions on two of the three rounds, and an even weighing on the third.  Group IV causes tips on only one round.

Within each group, there's room to make the three member balls tip on different rounds, since there are three rounds total.  Is that enough for a solution? Try it.  If not, scroll down.























OK.  Let Group I be balls 1, 2 and 3.  Let X be an unallocated ball - assume for now all Xs are "normal" and make sure if 1, 2 or 3 are oddballs, they'll be distinctive.  As a rule of thumb, it will be easier to fit all the balls where they need to be if we start with Group I and try to make each round and side roughly balanced.  To represent our schema, let's place 1, 2 and 3 in a grid like so (each row is a round of weighing):

X	X	X	1			2	3	X	X
X	X	X	2			1	3	X	X
X	X	X	3			1	2	X	X

So, Group I tips the scales 3 times, always.  We'll have to make sure *only* Group I tips the scales one direction or the other for all three rounds.  Moreover, 1 tips the scales in a different way the 1st round, 2 tips the scales in a different way the 2nd time, and 3 tips the scales in a different way the 3rd time, so once we know it's a Group I ball, we can distinguish 1, 2 and 3.  Finally, we can tell if the oddball is heavier or lighter by looking at the way the scales tip.  Also note that each round includes all of the Group I balls: this is necessary so that any Group I ball tips the scales each time.

On to Group II: balls 4, 5 and 6.  They all tip the scales the same way 2 out of 3 times; let 4 not tip the scales the first round, 5 not tip the scales the second round, and 6 not tip the scales the third round.  Then one way of doing things is:

X	6	5	1			2	3	X	X
X	6	4	2			1	3	X	X
X	X	4	3			1	2	5	X

Again, *only* group II balls  tip the scales precisely twice with the tips in the same direction.  Knowing which round there was no tip, you can distinguish 4, 5 and 6, and looking at the way the scales tipped tells you if the oddball's lighter or heavier.

Group III is like Group II in that the scales tip 2 out of 3 rounds, but for Group III the scales tip in *different* directions for the two times they tip.  That distinguishes Group II from Group III, and further we can distinguish between Group III's 3 members by looking at which of the 3 rounds had a neutral weighing.  As before, let 7 not tip the 1st round, 8 not tip the second round, and 9 not tip the third:

X	6	5	1			2	3	8	9
9	6	4	2			1	3	7	X
8	7	4	3			1	2	5	X

Group IV is now a cinch: they just tip the scales once.  Let 10 tip on the first round, 11 on the second, and 12 on the third:

10	6	5	1			2	3	8	9
9	6	4	2			1	3	7	11
8	7	4	3			1	2	5	12

There you have it!  With the above weighing schedule, perform the following:

1. If the scales tip 3 times, the oddball is in Group I (1, 2 or 3)
2. If they tip twice in the same direction, the oddball's in Group II (4, 5 or 6)
3. If they tip twice in different directions, the oddball's in Group III (7, 8 or 9)
4. If they tip once, the oddball's in Group IV (10, 11 or 12)

 In each case, you can tell which of the three Group members is the oddball, and whether it's heavier or lighter than the rest, based on the tips.

There you have it: a principled way to solve the 12 ball problem.  Much more satisfying than trial and error, don't you agree?

Edit:  I've used 24 of the 27 conceivable observations: the patterns CCC, LLL and RRR are never used.  It's possible to use LLL or RRR (for example, switch the left 4 balls with the right 4 balls on the first round and 1 will yield RRR or LLL depending on whether it's heavy or light), CCC can never be useful since it can never tell you if the oddball is heavier or lighter than the rest.