12 ball problem again

Hi again,

I just thought I'd let you know I found an even better, more general solution to the 12 ball problem mentioned yesterday, generalized to (3^N-3)/2 balls where N = the number of weighings.  Check it out here:

Here's the solution to the n-weighing version of this problem that
I said I'd recently read. It was found by Dyson and Lyness in 1946;
I think I've improved the exposition. I'll explain it for the original
problem first, and then explain the generalization.

Label the 12 coins by the sequences

AAB ABA ABB ABC BBC BCA BCB BCC CAA CAB CAC CCA

and in the

1st AAB ABA ABB ABC BBC BCA BCB BCC
2nd weighings put AAB CAA CAB CAC in pan A, ABA ABB ABC BBC in pan B.
3rd ABA BCA CAA CCA AAB ABB BCB CAB

Now in a given weighing, a pan will either end up in the

Canonical position (C) that it assumes when the pans are balanced, or
Above that position (A), or
Below it (B),

so the weighings determine a sequence of three of these letters.

If this sequence is CCC, then there's no fake coin. Otherwise,
for just one of the two pans the sequence is among the 12 above,
and names the fake coin, whose weight is Above or Below the proper
one according as the pan is A or B.

N weighings can be used to locate a possible fake from among
(3^N - 3)/2 coins in the same way, by labelling them with all
the non-constant sequences of N letters from A,B,C whose
first change is A-to-B or B-to-C or C-to-A, and at the
kth weighing putting those whose kth letter is A in pan A
and those whose kth letter is B in pan B.

Neat, isn't it?

John Conway

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.