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 ith measure the jth coin is put to the left;
-1 if in the ith measure the jth coin is put to the right;
0 if the jth coin is not used in the ith measure.
The jth column of the table will be denoted by vj.
We can encode the results of measures in another k-vector r. The ith coordinate of r means the result of the ith 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 fth and it is heavier than the others, we have r=vf. If the coin is lighter than the rest, we have r=-vf.
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 v1+v2+...+vn=0.
(2) The vectors v1,-v1,v2,-v2,...,vn,-vn must be pairwise distinct. (This also implies that vj 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 v1,...,vn for a value k, then for k+1 take the vectors , and for every j=1,2,...,n, and take , and .