Café Math : Weighting Bags

[C# source code available here]

Hi, today my colleague Stuart told me about the following brain teaser of combinatorics. I've found it pretty interesting.

Problem. Suppose you have twelve bags and a scale. All of the bags weight the same, except for one which is either lighter or heavier than the others. You have to determine which is that bag and if it is heavier or lighter in only three weightings.

One weighing has *three* different possible outcomes: either the two plates of the scale are equally heavy,
or the left one is heavier or it is lighter.
The first idea that comes to mind, is to do a first weighting and then, to arrange the next weighting according
to the outcome of the first, and then to arrange the third according to the outcome of the first two.
This leads to a complicated decision tree of essentially *one* plus *three* plus *nine* configurations that
have to separate all of the *twenty four* cases.

Instead of doing that, let's see if we can arrange the three weightings independently of each other, in such a way that the three outcomes separate the twenty four cases. It is not at all obvious from the begining that this is at all possible, but the pleasant surpise is that it is.

So the idea is to label the bags from $1$ to $12$ and for each weighting, partition the set $\{1, ..., 12\}$
in three different parts, one for the bags we put on the left plate of the scale, one for those we put
on the right plate, and one for those we leave aside.
To further narrow the search, we suppose that those three parts are each of size *four*, that is we put *four*
bags on each plate for each weigting. Say we represent a weighting strategy with an array as follows,
\begin{align*}
[L, L, L, L, -, -, -, -, R, R, R, R] \\
[L, L, L, R, -, R, R, R, L, -, -, -] \\
[L, -, R, L, R, L, -, R, -, L, -, R]
\end{align*}
where each line is a single weighting, each column correspond to a specific bag.
This array tells which bags we put left, right or aside for each of the three weighting.
Say the bag that is different is actually *heavier* than the others. One can
readily read the outcome of those weighting from the array itself, and so each column tells
the result of the experiment for each of the twelve cases. to be able to decide which bag was heavier
those twelve columns have to be different from one another.
Now if the bag was lighter, the result of the experiment would get inverted, in the sense that
this would replace $L$ by $R$ and $R$ by $L$, as follows.
\begin{align*}
[R, R, R, R, -, -, -, -, L, L, L, L] \\
[R, R, R, L, -, L, L, L, R, -, -, -] \\
[R, -, L, R, L, R, -, L, -, R, -, L]
\end{align*}
In order to be able to decide if the bag was actually heavier or lighter, those columns all have to
be different from those of the previous array. Let's summerize the constraints as follows,

- Four $L$, four $R$ and four $-$ on each rows.

- No two identical columns.

- No column equal to the oposite of one column (the opposite is when one replaces $R$ by $L$ and $L$ by $R$).

- No column consist of only $-$. That would mean that a bag is never weighted and then one can't decide if
it is heavier or lighter than the others.

- One decide of a total order on the set of possible columns and say we are only interested in arrays for which the sequence of columns is increasing.

Using the C# source code provided [here] I got $304$ different solutions satisfying the five above constraints. The program run in less than two seconds. It means that by permuting the columns of those solutions one obtain, $$ 304 \cdot 12! = 145616486400 $$ distinct solutions. [Output of the program here]

Let's consider the polynomial algebra with nine commutative variables, $$\mathbb{Z}[x_{a}, y_{a}, z_{a} | a\in \{-1,0,1\} ].$$ Let's consider the following code, $$ c_{a_1 + 3 a_2 + 9 a_3} = x_{a_1}y_{a_2}z_{a_3} $$ where $a_1, a_2, a_3 \in \{ -1, 0, 1 \}$. Then the number of solution of the above problem subject to the five metionned constraints, is the coefficient of the monomial, \begin{align*} \prod_{ a\in \{-1,0,1\}} x_{a}^4 y_{a}^4 z_{a}^4 \end{align*} in this expression, \begin{align*} \prod_{k=1}^{13} (1 + c_k + c_{-k}) \end{align*} or, equivalently, in this expression, $$ \sum_{k = 1}^{13} \frac{1}{c_k + c_{-k}} \prod_{\ell = 1}^{13} (c_\ell + c_{-\ell}) $$ which has much less terms in developped form, albeit being less simple looking. The answer we get is $304$, which confirms that the program finds the correct number of solutions. This of course, doesn't tell us that the program is correct. A number of thing could go wrong. For example, in the set of solutions, one could find pairs of identical solutions, or one could find arrays that don't satisfy the constraints, etc... So the mere fact that the number of solutions produced by the program is correct is just a confirmation but of little value.

The thing is that now, verifying that the candidate solutions produced by the program indeed satisfy the constraints, is mechanical and can be programmed easily. Verifying that all the produced solutions are distinct from one another is again not too hard. A key property, to speed up that verification, is that there is a lexicographic order on the solutions and that the program actually outputs them in that order. If the sequence of solution outputed by the program is strictly increasing then there is no doubt they are all unique. So that's the easy part. Now how can we know that we don't miss any solution ? That could be hard. But since we know that the solution given by the program are unique, we can use the Dirichlet principle,

Theorem (*Dirichlet*).*
Let $f:X \rightarrow Y$ be a mapping between two finite sets of the same cardinal. The following
propositions are equivalent,
*

*$f$ is**injective*.*$f$ is**surjective*.*$f$ is**bijective*.

Indeed, the fact that the program outputs candidates that satisfy the constraints, says that
this realizes a mapping to the set of solution to the problem. The fact that the sequence of solutions
is strictly increasing and thus that they are distinct, says that this mapping is injective.
Since the above computation shows that the two sets have
$304$ elements each, the theorem implies that the mapping is *surjective*.