Café Math : Weighting Bags

# Weighting Bags

### Thu, 11 Sep 2013 01:09:11 GMT

[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,

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

2. No two identical columns.

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

4. 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.

5. 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.
Condition 5. guaranties that we consider one and only one solution in each orbit of the permutation group $\mathfrak{S}_{12}$.

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]

# 1. Counting Solutions Using Algebra

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.

# 2. Enumeration Principle Correctness

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,

1. $f$ is injective.
2. $f$ is surjective.
3. $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.