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.

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.

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 i-th 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 i-th weighting on the left scale all the balls that have an L in the i-th position and on the right scale all the balls that have an R in the i-th 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.

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.

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:

 

 

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^n-3)/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 non-independent 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.

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.

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.

Links

Discussion by Brian Bundy

Solution by Donald Newman

Solution by W. McWorter

Discussion by Unknown

Solution by John Conway