Problem A. 512. (September 2010)

A. 512. We have $n=\frac{3^k-3}2$ 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 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 v_j.

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=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₁+v₂+...+v_n=0.

(2) The vectors v₁,-v₁,v₂,-v₂,...,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 $\left(\matrix{0\cr 0\cr \vdots\cr 0}\right)$ , $\left(\matrix{+1\cr +1\cr \vdots\cr +1}\right)$ and $\left(\matrix{-1\cr -1\cr \vdots\cr -1}\right)$ , is the following.

For k=2 and n=3, let $v_1=\left(\matrix{-1\cr 1}\right)$ , $v_2=\left(\matrix{1\cr 0}\right)$ and $v_3=\left(\matrix{0\cr -1}\right)$ .

If we already have some vectors v₁,...,v_n for a value k, then for k+1 take the vectors $\left(\matrix{v_j\cr +1}\right)$ , $\left(\matrix{v_j\cr -1}\right)$ and $\left(\matrix{v_j\cr 0}\right)$ for every j=1,2,...,n, and take $\left(\matrix{-1\cr -1\cr \vdots\cr -1\cr +1}\right)$ , $\left(\matrix{+1\cr +1\cr \vdots\cr +1\cr 0}\right)$ and $\left(\matrix{0\cr 0\cr \vdots\cr 0\cr -1}\right)$ .

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

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.

Already signed up?
New to KöMaL?