6. A train consists of $n>1$ waggons with gold coins. Some coins are genuine and some are fake, although they all look the same and can only be distinguished by mass: all genuine coins have the same mass, and so do all fake ones, where the two masses differ. The mass of a genuine coin is known. Each waggon contains only genuine coins or only fake ones.

Find the smallest number of measurements on a digital scale by which one can determine all waggons with fake coins and find the mass of a fake coin.

(It is assumed that from each waggon one can take as many coins as needed.)

(Miloš Milosavljević)

Time allowed: 270 minutes.

Each problem is worth 7 points.
6. We show that the smallest number of measurements is 2 . Denote the masses of a genuine and fake coin by $x$ and $y$ respectively, and let $a_{i}=1$ if the $i$-th waggon contains genuine coins, and $a_{i}=0$ otherwise.

In the first measurement, take one coin from each waggon; let $m_{1}$ be the result. Then $a_{1}+a_{2}+\cdots+a_{n}=\frac{n x-m_{1}}{x-y}$. We assume that $m_{1} \neq n x$, for there would be no fake coins otherwise. In the second measurement, for a suitable $q \in \mathbb{N}$, take $q^{i-1}$ coins from the $i$-th waggon; let $m_{2}$ be the result. We have $a_{1}+q a_{2}+\cdots+q^{n-1} a_{n-1}=$ $\frac{\left(1+q+\cdots+q^{n-1}\right) x-m_{2}}{x-y}$. This yields

$$
f\left(a_{1}, a_{2}, \ldots, a_{n}\right)=\frac{a_{1}+q a_{2}+\cdots+q^{n-1} a_{n-1}}{a_{1}+a_{2}+\cdots+a_{n}}=\frac{\left(1+q+\cdots+q^{n-1}\right) x-m_{2}}{n x-m_{1}}
$$

If we can choose $q \in \mathbb{N}$ such that the function $f:\{0,1\}^{n} \backslash\{(0,0, \ldots, 0)\} \rightarrow \mathbb{R}$ is injective, this will mean that the value of $f$ will uniquely determine $a_{1}, \ldots, a_{n}$, i.e. the waggons with fake coins, and finally $y=x-\frac{n x-m_{1}}{a_{1}+a_{2}+\cdots+a_{n}}$.

For fixed $\mathfrak{a}=\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ and $\mathfrak{a}=\left(b_{1}, b_{2}, \ldots, b_{n}\right)$, the equality $f(\mathfrak{a})=f(\mathfrak{b})$ is equivalent to $P_{\mathfrak{a}, \mathfrak{b}}(q)=\left(a_{n} b-b_{n} a\right) q^{n-1}+\cdots+\left(a_{2} b-b_{2} a\right) q+\left(a_{1} b-b_{1} a\right)=0$, where $a=a_{1}+a_{2}+\ldots+a_{n} \neq 0 \neq b_{1}+b_{2}+\ldots b_{n}=b$. Therefore, if $f$ is not injective, then $q$ is a zero of the polynomial $P(q)=\prod_{\mathfrak{a}, \mathfrak{b}} P_{\mathfrak{a}, \mathfrak{b}}(q)$. Since the polynomials $P_{\mathfrak{a}, \mathfrak{b}}$ are nonzero, there are only finitely many numbers $q$ with $P(q)=0$, so there exists $q$ for which $f$ is injective, proving that two measurements are enough.

One measurement is not enough. Taking $k_{i}$ coins from the $i$-th waggon yields the equation $k_{1} a_{1}+\cdots+k_{n} a_{n}=\frac{k x-m}{x-y}$ (where $k=k_{1}+\cdots+k_{n}$ ) which does not have a unique solution: for instance, both $\left(1,0, \ldots, 0, x-\frac{k x-m}{k_{1}}\right)$ and $\left(0,0, \ldots, 1, x-\frac{k x-m}{k_{n}}\right)$ are possible solutions for $\left(a_{1}, a_{2}, \ldots, a_{n}, y\right)$.

The 29-th Balkan Mathematical Olympiad was held from April 26 to May 2 in Antalya in Turkey. The results of Serbian contestants are given in the following table:

|  | 1 | 2 | 3 | 4 | Total |  |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| Teodor von Burg | 10 | 10 | 10 | 10 | 40 | Gold Medal |
| Dušan Śobot | 10 | 10 | 10 | 10 | 40 | Gold Medal |
| Igor Spasojević | 10 | 10 | 10 | 10 | 40 | Gold Medal |
| Rade Śpegar | 10 | 10 | 10 | 8 | 38 | Silver Medal |
| Ivan Damnjanović | 0 | 10 | 10 | 1 | 21 | Bronze Medal |
| Ivan Tanasijević | 10 | 10 | 0 | 0 | 20 | Bronze Medal |

After the contest, 14 contestants (13 officially +1 unofficially) with 39-40 points were awarded gold medals, 28 (10+18) with $30-38$ points were awarded silver medals, and $45(19+26)$ with $20-28$ points were awarded bronze medals.

The unofficial ranking of the teams is given below:

| Member Countries | Guest Teams |  |  |
| :--- | ---: | :--- | ---: |
| 1. Turkey | 226 | Turkey B | 196 |
| 2. Romania | 213 | Italy | 172 |
| 3. Serbia | 199 | France | 161 |
| 4. Bulgaria | 162 | Kazakhstan | 156 |
| 5. Greece | 154 | United Kingdom | 139 |
| 6. Bosnia-Herzegovina | 140 | Tajikistan | 138 |
| 7. Moldova | 133 | Saudi Arabia | 131 |
| 8. Macedonia (FYR) | 109 | Turkmenistan | 107 |
| 9. Cyprus | 79 | Azerbaijan | 83 |
| 10. Albania | 41 | Indonesia | 68 |
| 11. Montenegro | 16 | Afghanistan | 0 |