**Outline of solution. **The measures will be listed in a *k*×*n* table. Each column will refer to a coin and each row defines a measure. The (*i*,*j*)th entry will be:

+1 if in the *i*th measure the *j*th coin is put to the left;

-1 if in the *i*th measure the *j*th coin is put to the right;

0 if the *j*th coin is not used in the *i*th measure.

The *j*th column of the table will be denoted by *v*_{j}.

We can encode the results of measures in another *k*-vector *r*. The *i*th coordinate of *r* means the result of the *i*th measure; it is 1 if the left-side is heavier, -1 if the right-hand side is heavier and 0 if we have balance.

If the counterfeit coin is the *f*th and it is heavier than the others, we have *r*=*v*_{f}. If the coin is lighter than the rest, we have *r*=-*v*_{f}.

So, what properties do we expect from the table *T*?

(1) In each row, the sum must be 0, because the same number of coins is put to the left and right balances. So *v*_{1}+*v*_{2}+...+*v*_{n}=0.

(2) The vectors *v*_{1},-*v*_{1},*v*_{2},-*v*_{2},...,*v*_{n},-*v*_{n} must be pairwise distinct. (This also implies that *v*_{j} cannot be the zero vector.)

Such a table (set of vectors) can be constructed in many ways. For example, you can apply greedy methods when those vectors are selected later which contain less nonzero entries.

An inductive costruction, which does not use the vectors , and , is the following.

For *k*=2 and *n*=3, let , and .

If we already have some vectors *v*_{1},...,*v*_{n} for a value *k*, then for *k*+1 take the vectors , and for every *j*=1,2,...,*n*, and take , and .