Weighing 12 Balls
Do I have another version of this stuff somewhere? Where is the paper stuff where I computed the orbits? Incorporate the gap code?
The problem
Suppose you have 12 balls, numbered 1 to 12. You know that one of them is lighter or heavier than the other 11. You are given a balance scale and you may perform three (or fewer) measures to find the special ball, and to find out whether it is lighter or heavier than the other balls.
What measurements do you perform?
The solution
Perform the following three weightings.
weighting 
left 
right 
1 
6, 8, 10, 12 
5, 7, 9, 11 
2 
3, 5, 7, 12 
2, 4, 6, 11 
3 
2, 5, 10, 11 
1, 4, 7, 8 
After the three weightings write down the result as a word of three letters: L if the scale turns left, R if the scale turns right, and N if the scale stays in balance.
Then look up the result in the following matrix. Find the word and the row tells you which ball is special and the column tells you whether it is heavier of lighter.
ball 
heavier 
lighter 
1 
NNR 
NNL 
2 
NRL 
NLR 
3 
NLN 
NRN 
4 
NRR 
NLL 
5 
RLL 
LRR 
6 
LRN 
RLN 
7 
RLR 
LRL 
8 
LNR 
RNL 
9 
RNN 
LNN 
10 
LNL 
RNR 
11 
RRL 
LLR 
12 
LLN 
RRN 
We call this matrix the solution matrix.
Independent weighings
First note that the solutions consists of three independent weightings. That means that the second weighting does not depend on the first, and the third does not depend on the first two.
In other solutions the second weighting depends on the first, i.e., what you put on the scale depends on the output of the first weighting and so on. I.e. such solutions have the following form.
First measure 1,2,3,4 against 5, 6, 7, 8;
if the scale turns left, then measure this
if the scale turns right, then measure that
else measure something.
It turns out, that solutions with independent weightings are just as powerful and easier to investigate.
Properties of the solutions matrix
The solutions matrix has the following properties

Each word appears only once

The two words in a row a complements (where L is replaced by R, and vice versa)

In the ith position of the words in each column we have the same number of Ls and Rs
From the solution matrix we get the weighting instruction by placing in the ith weighting on the left scale all the balls that have an L in the ith position and on the right scale all the balls that have an R in the ith position.
The first condition means that we can uniquely tell which ball is lighter or heavier for each possible outcome.
The second condition is obviously necessary. If we take a certain ball the two possibilities (that it is lighter or heavier) will result in exactly opposite results for each weighting where this ball is placed on one of the scales.
The third condition means that we put the same number of balls on the left and the right scale for each weighting.
So those three conditions are obviously necessary for a solution matrix.
How to construct a solution matrix
On the other hand it is easy to see, that we get a solution from each matrix with the above three properties. So the question is, how do we construct a matrix which satisfies the above three conditions.
The second condition says that in each row we have complement words. There are 13 pairs of complement words.
So we must leave out one pair. This must be a pair with no Ns in it, otherwise in one weighting we have 9 balls (corresponding to the 9 entries that are not N in this position). Without loss of generality (for each of the three positions we can exchange L and R in this position, corresponding to exchanging the left and the right side for this weighting) we can leave out the pair LLL, RRR.
So if we take the remaining 12 pairs of complement words we have a matrix that satisfies the first two properties. Again without loss of generality (we can renumber the balls), we start in the left column with NNR, go up lexicographically, and end with RRN in the left column.
ball 
heavier 
lighter 
1 
NNR 
NNL 
2 
NRL 
NLR 
3 
NRN 
NLN 
4 
NRR 
NLL 
5 
RLL 
LRR 
6 
RLN 
LRN 
7 
RLR 
LRL 
8 
RNL 
LNR 
9 
RNN 
LNN 
10 
RNR 
LNL 
11 
RRL 
LLR 
12 
RRN 
LLN 
Now we must select a set of rows where we exchange the left and the right word, so that we end up with a matrix that also satisfies the third condition.
There are several (76?) ways to do this. One is given above, another is given below.
Alternative Solution
In the following solution the rows where we switch the left and the right are choosen such that the first transition to a different letter goes from N to R, from R to L, or from L to N.
ball 
heavier 
lighter 
1 
NNR 
NNL 
2 
NRL 
NLR 
3 
NRN 
NLN 
4 
NRR 
NLL 
5 
RLL 
LRR 
6 
RLN 
LRN 
7 
RLR 
LRL 
8 
LNR 
RNL 
9 
LNN 
RNN 
10 
LNL 
RNR 
11 
RRL 
LLR 
12 
LLN 
RRN 
It works, but I see no easy argument why. Note that this is also the solution where we exchange as far down as possible (8, 9, 10, 12).
It works because with every vector (on the left side) we also have the other two vectors under the permutation (conjugation) (N,R,L) on the left side. Those three vectors in one orbit always add up to (0,0,0). The orbits are [[1,11,12],[2,6,8],[3,7,10],[4,5,9]].
Yet another Solution
Actually this is the same solution as above. Just described slightly differently.
In this solution we arrange the weightings such that we can easily compute which ball is heavier or lighter:
B = 0;
weigh 5,6,7,11 / 8,9,10,12; if left then B += 9; if right then B = 9;
weigh 2,3,4,11 / 5,6,7,12; if left then B += 3; if right then B = 3;
weigh 1,4,7,8 / 2,5,10,11; if left then B += 1; if right then B = 1;
abs(B) is the ball that is heavier or lighter;
if B in [1,2,3,4,5,6,7,8,9,10,11,12] then it is heavier; else lighter;
The solution matrix for this solution is:
ball 
heavier 
lighter 
1 
0 0 1 
0 0 1 
2 
0 1 1 
0 1 1 
3 
0 1 0 
0 1 0 
4 
0 1 1 
0 1 1 
5 
1 1 1 
1 1 1 
6 
1 1 0 
1 1 0 
7 
1 1 1 
1 1 1 
8 
1 0 1 
1 0 1 
9 
1 0 0 
1 0 0 
10 
1 0 1 
1 0 1 
11 
1 1 1 
1 1 1 
12 
1 1 0 
1 1 0 
It is constructed by taking the nonzero vectors in the order of their absolute value and putting on the left side those with first transition 0 > 1 > 1 > 0.
Basically you get this solution matrix if you write down the numbers [1,2,3,4,5,6,7,8,9,10,11,12] using +9/0/9 + +3/0/3 + +1/0/1. A nicer solution might be to write down [1,2,3,4,5,6,7,8,9,10,11,12]. This also gives a valid solution matrix.
The total number of solutions
All in all there are 145’616’486’400 solution matrices, which we can enumerate as follows:

the 76 possibilities to switch left and right word for certain balls, so that in each position we have the same number of Ls and Rs,

the 4 possibilities which of the four pairs (LLL,RRR; LLR,RRL; LRL,RLR; LRR,RLL) to leave out (this corresponds to the 4 possible switches between left and right scale for the second and third measurement, we do not switch between left and right scale for the first measurement because switching for all three measurements corresponds to switching left and right word for all balls, i.e., something we already counted in the first point),

the 12! possible renumberings of the balls.
Under the equivalence operations: exchanging left and right side for some measurements and renumbering the balls there are 38 orbits of 8 * 12! solutions each.
Is there some easy argument that shows what those 38 orbits are?
How do those orbits merge under the equivalence operation that exchanges the order of the measurements? I would guess 2, 6, 6, 6, 6, 6, 6?
Is there some easy argument that shows what those orbits are?
Generalizations
In general we can handle (3^n3)/2 balls with n weighings.
Is it possible to handle 13 balls?
At first it would appear that it is possible to handle 13 balls with three weighings. There are 26 possibilities (13 balls * 2 possibilities) and 27 different outcomes (3 weightings ^ 3 possibilities).
However it turns out, that it is not possible. This is because for a solution we would need a solution matrix with 13 rows with the above three properties. But every matrix that we get from taking the 13 pairs of words tries to weigh 9 balls with each weighing (that is the number of L or R in each position).
Another proof also works when we allow nonindependent weightings. In the first weighting we could weight 4 balls against 4 other balls. If the scale stays balanced, we have 5 balls times 2 possibilities, which we could not solve with the two remaining weightings. Or we weight 5 balls against 5 balls. If the balance turns left we have again 10 possibilities (one of the 5 balls on the left scale is heavier or one of the 5 balls on the right scale is lighter), which we again could not solve with the two remaining weightings.
However there are slight modifications of the original problem that have solutions.
One way to handle 13 balls is if we have an extra ball (14) of correct weight. Than we add the following two rows to the above solution matrix.
13 
LLL 
RRR 
14 
RRR 
LLL 
Because we know that ball 14 has the correct weight, the result LLL tells us that ball 13 is heavier and the result RRR tells us that ball 13 is lighter.
Another way to handle 13 balls is if we need not determine whether this ball is heavier or lighter. Than we add the following row to the solution matrix.
13 
NNN 
NNN 
If the scale remains balanced in all three weightings we know that the 13th ball is the odd ball, but we cannot tell wether it is lighter or heavier.