We are given $n>1$ piles of coins. There are two different types of coins: real and fake coins; they all look alike, but coins of the same type have the same mass, while the coins from different types have different masses. Coins that belong to the same pile are of the same type. We know the mass of real coin. Find the minimal number of weightings on digital scale that we need in order to conclude: which piles consists of which type of coins and also the mass of fake coin. (We assume that every pile consists from infinite number of coins.)
Problem
Source: Serbian National Olympiad 2012, Problem 6
Tags: combinatorics, weights
07.04.2012 20:57
Can their mass being irrational ? or It's integer ?
07.04.2012 21:27
If I understand the problem correctly, the answer is 2. Let the weight of the real coins be $x$ and that of the fake be $y$. This solution works regardless of whether $x,y$ are specified to be integers or reals. To show 1 use is not enough, suppose our only weighing is with $a_i$ coins taken from pile $i$. This can't distinguish between the cases where $y = x + a_2$ and pile 1 is the only one with fake coins, or where $y = x + a_1$ and pile 2 is the only one with fake coins. For 2 uses of the scale to work, first weigh one coin from each pile. If we get weight $nx$, all coins are real. Otherwise, we get a weight $nx + \delta$ for some error $\delta$ (positive or negative). Then we know $y-x = \delta/j$ for some $j \in \{1,2, \ldots n\}$. Now do a weighing with $k^{i-1}$ coins taken from pile $i$ for $i = 1, 2, \ldots n$, where $k$ is an integer greater than $n^2 + 1$. The total where all coins are real would be $W = \frac{k^n-1}{k-1} x$. If pile $i$ contains the fake coins, this will offset us from $W$ by at least $a_i = k^{i-1}|\delta|/n$ and at most $b_i = k^{i-1}|\delta|$. Now note that \[a_{i+1} = \frac{k^i |\delta|}{n} > n\frac{(k^i - 1) |\delta|}{k-1} = n|\delta| (k^{i-1} + k^{i-2} + \cdots + 1) = n(b_i + b_{i-1} + \cdots + b_1).\] Therefore, if $W'$ is the weight we actually got on the second weighing, we can take the maximum $i$ such that $|W - W'| > a_i$ and know from this that pile $i$ is fake while piles $i+1$ through $n$ are real. Therefore, $|W - W'| = k^i |\delta|/j + S$ ($\ast$) where $S$ is a nonnegative real with $S \leq b_{i-1} + b_{i-2} + \cdots + b_1 < \frac{k^i |\delta|}{n^2}$ ($S$ is the "error" resulting from piles $1$ through $i-1$). Since we know both $|W - W'|$ and $\delta$, and $|k^i \delta/m - k^i \delta/m'| > S$ for any distinct $m,m' \in \{1, 2, \ldots n\}$, there is only one possibility for $j$ that can satisfy ($\ast$) and thus we can find what $y$ is. Determining which piles are which from this is easy.