1. Non-Adaptive Weighing

We seek to find one bad coin out of n potentially bad ones, (given one good one,) and we know that the bad coin is either heavy or light. We have a balance to determine the bad one.

We want to use as few weighings as we can.

Our plan is to state in advance exactly which coins we will put on each side of the balance at each weighing, independent of what we learn from the previous ones. This is kind of dumb, but there it is.

If we state in advance which coins will be put where, the result can be described by putting a 1 in the j-th row and i-th column of a matrix, if the ith coin goes on the left of the scale on that weighing, putting a -1 there if it goes on the right on that weighing, and putting a 0 if it is off the scale in that weighing.

We want to construct a matrix that can do the most for k weighings.

What conditions must our matrix obey?

1. It is a matrix with k rows consisting of 1’s, -1’s and 0’s.

2. Each row must sum to zero. (This represents the fact that unless we put the same number of coins on each side of the balance, we will learn nothing at all from its balance state.)

3. No two columns can be the same. (Otherwise we could not distinguish which of the corresponding coins were bad, if one or the other was.)

4. No two columns can be negatives of one another. (Otherwise we could not distinguish if one of the corresponding coins was light from the other being heavy.)

Wonderfully enough, if these conditions are obeyed, then we can distinguish which is the bad coin by examining the outcome of the experiment and comparing it with the columns; the column that it matches or is the negative of, is the bad coin.

If we have a guaranteed good coin, its column can be the same or opposite of another, since we know by definition that it cannot be the bad coin.

Our plan is to construct a matrix inductively, first for one weighing, and then two, three, etc. We will find a scheme that always works, and gives an optimal solution. By the way, that means that if there are n potentially bad coins and one good one then (2n-1) is at most 3 to the power k.

What can we do with one weighing?

g 1 2

______

1 -1 0

Without a good coin we are dead in the water; with one we can distinguish among two coins, as in the matrix above.

Notice that 2 is the upper bound here.

Now what can we do with a second weighing, or second row?

The most we could dream of doing is to put 0 1 and -1 beneath each of the entries above. This will give rise to 9 columns including g which is 3 too many. And we find that condition 4. is violated in three places:

g 1 2 3 4 5 6 7 8

_____________________

1 -1 0 1 -1 0 1 -1 0

1 1 1 -1 -1 -1 0 0 0

Namely, columns 1 and 3 are negatives of each other, and likewise 6 and 7 and 2 and 5.

We obtain an optimal solution if we can eliminate one from each pair so that the remaining rows still sum to 0 as they do above. The wonderful thing is that we can not only do so, but we can do so in a way that works just as well in going from 2 to 3 rows or from k to k+1 rows, as it does here in going from 1 to 2 rows. This means we have a procedure for constructing an optimal non-adaptive weighing scheme for any number of weighings: To construct one for k rows, take the one you construct for k-1, repeat it thrice with 1, -1 and 0 beneath, and remove three appropriate columns.

Which three columns? well, one of the three bad pairs above has no 0’s in it (above it is 1 and 3). Choose one of these, say 1. Find the members of the other two pairs that are negatives of its entries (here 5 and 6) and choose those also. Toss those three out. The rest obeys all conditions, and has maximum number of columns.

You should try this explicitly for k=3 and if you are a skeptic, for k=4.

It does not immediately follow that you can do everything you want non-adaptively, because you might have fewer coins than the maximum, and not have good coins. You can actually always handle any case (except that to get the maximum allowed by the bound you need one good coin), but that is not obvious because simply throwing away columns will violate the rows-sum-to-0 condition.

However, you are free to throw away columns and also reverse the sign of others in attempting to get row sums to be 0,and that seems always to be possible.

Exercise: Verify this last claim for n = 9,10, and 11; by producing three-row matrices without a good coin having the said number of columns, obeying the conditions above.