Maths Olympiad Prep

Library / /83 of 87

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Serbia

Problem:

Let a train consist of n>1n>1 wagons with gold coins. There are two types of seemingly identical coins: genuine and counterfeit. Each wagon contains coins of only one type. Coins of the same type have the same mass, while coins of different types do not have the same mass. The mass of a genuine coin is known.
Determine the minimum number of measurements on a digital scale by which it is possible to determine which wagons contain counterfeit coins, as well as what the mass of a counterfeit coin is.
(It is assumed that any number of coins can be taken from each wagon.)
(Miloš Milosavljević)

Solution

Solution:

We will prove that the minimum number of measurements equals 2. Denote the weights of a genuine and a counterfeit coin by xx and yy respectively, and let ai=1a_{i}=1 if the coins in the ii-th wagon are counterfeit, and ai=0a_{i}=0 otherwise.

In the first measurement, take one coin from each wagon. Then a1+a2++an=nxm1xya_{1}+a_{2}+\cdots+a_{n} = \frac{n x - m_{1}}{x-y}, where m1m_{1} is the obtained mass. We assume that m1nxm_{1} \neq n x, since otherwise there are no counterfeit coins.

In the second measurement, for some qNq \in \mathbb{N}, we take qi1q^{i-1} coins from the ii-th wagon. If the obtained mass is m2m_{2}, we have a1+qa2++qn1an=(1+q++qn1)xm2xya_{1} + q a_{2} + \cdots + q^{n-1} a_{n} = \frac{(1+q+\cdots+q^{n-1}) x - m_{2}}{x-y}. From here we obtain
f(a1,a2,,an)=a1+qa2++qn1ana1+a2++an=(1+q++qn1)xm2nxm1 f\left(a_{1}, a_{2}, \ldots, a_{n}\right) = \frac{a_{1} + q a_{2} + \cdots + q^{n-1} a_{n}}{a_{1} + a_{2} + \cdots + a_{n}} = \frac{(1+q+\cdots+q^{n-1}) x - m_{2}}{n x - m_{1}}
We want the value of ff to uniquely determine a1,,ana_{1}, \ldots, a_{n}. Thus, it suffices to show that there exists a natural number qq such that the function f:{0,1}n{(0,0,,0)}Rf:\{0,1\}^{n} \setminus \{(0,0, \ldots, 0)\} \rightarrow \mathbb{R} is injective.

For fixed a=(a1,a2,,an)\mathfrak{a} = (a_{1}, a_{2}, \ldots, a_{n}) and b=(b1,b2,,bn)\mathfrak{b} = (b_{1}, b_{2}, \ldots, b_{n}), the equality f(a)=f(b)f(\mathfrak{a}) = f(\mathfrak{b}) is equivalent to Pa,b(q)=(abnban)qn1++(ab2ba2)q+(ab1ba1)=0P_{\mathfrak{a}, \mathfrak{b}}(q) = (a b_{n} - b a_{n}) q^{n-1} + \cdots + (a b_{2} - b a_{2}) q + (a b_{1} - b a_{1}) = 0, where a=a1+a2++an0b=b1+b2++bna = a_{1} + a_{2} + \ldots + a_{n} \neq 0 \neq b = b_{1} + b_{2} + \ldots + b_{n}. Therefore, if the function ff is not injective, then qq is a root of the polynomial
P(q)=a,bPa,b(q) P(q) = \prod_{\mathfrak{a}, \mathfrak{b}} P_{\mathfrak{a}, \mathfrak{b}}(q)
Since none of the polynomials Pa,bP_{\mathfrak{a}, \mathfrak{b}} is identically equal to 0, there are only finitely many numbers qq for which P(q)=0P(q) = 0, so it is possible to choose qq for which ff is an injective function.

In this way, in two measurements we can determine a1,,ana_{1}, \ldots, a_{n}, i.e., the wagons with counterfeit coins. Finally, we determine yy from the equality y=xnxm1a1+a2++any = x - \frac{n x - m_{1}}{a_{1} + a_{2} + \cdots + a_{n}}.

On the other hand, one measurement is not sufficient, because by taking kik_{i} coins from the ii-th wagon we obtain the equation k1a1++knan=kxmxyk_{1} a_{1} + \cdots + k_{n} a_{n} = \frac{k x - m}{x-y} (where k=k1++knk = k_{1} + \cdots + k_{n}) which in general has multiple solutions. For example, two possible solutions for (a1,a2,,an,y)(a_{1}, a_{2}, \ldots, a_{n}, y) are (1,0,,0,xkxmk1)(1, 0, \ldots, 0, x - \frac{k x - m}{k_{1}}) and (0,0,,1,xkxmkn)(0, 0, \ldots, 1, x - \frac{k x - m}{k_{n}}).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from sr; metadata (topic, difficulty) added by this project.