# Problem A. 512. (September 2010)

**A. 512.** We have coins, each one indistinguishable from the other in terms of size and appearance, but only *n*-1 of them have the same weight, whilst one of them is a counterfeit, being either lighter or heavier than the rest. Using a balance we have to find the counterfeit coin. Show that by *k* measurements it is possible to find the counterfeit coin and to determine whether it is heavier or lighter than the rest; moreover, it is possible to arrange the measurements in advance, without knowing the results of the measurements.

(5 pont)

**Deadline expired on October 11, 2010.**

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

### Statistics:

20 students sent a solution. 5 points: Ágoston Tamás, Damásdi Gábor, Frankl Nóra, Lenger Dániel, Mester Márton, Nagy 235 János, Nagy 648 Donát, Strenner Péter, Szabó 928 Attila, Viharos Andor. 4 points: Gyarmati Máté, Zsakó András. 3 points: 2 students. 2 points: 1 student. 1 point: 1 student. 0 point: 4 students.

Problems in Mathematics of KöMaL, September 2010