Dima has 100 rocks with pairwise distinct weights. He also has a strange pan scales: one should put exactly 10 rocks on each side. Call a pair of rocks {\it clear} if Dima can find out which of these two rocks is heavier. Find the least possible number of clear pairs.
Problem
Source: IV Caucasus Mathematic Olympiad
Tags: combinatorics, Kvant
09.04.2019 13:48
bump!!!!
27.09.2019 00:48
\textbf{Answer}. $\binom{100}{2}-\binom{19}{2}=4779$. \textbf{Solution.} A pair of rocks is called \textit{bad} if it is not clear. \textit{Example.} There are a set of 100 rocks containing a subset of 19 rocks such that any two rocks in the subset form a bad pair. Let the weights of rocks be equal to $100, 200, 400, \dots$, $2^{80}\cdot 100$, $2^{100}+1, 2^{100}+2,\dots, 2^{100]+19$. A rock is of weight more than $2^{100}$ is called \textit{heavy}, otherwise it is \textit{light}. We claim that it is impossible to distinguish heavy rocks even if we weight all possible pairs of subsets of 10 rocks using our pan scale. The following obvious facts easily imply the claim. \textit{Fact 1.} If a set of 10 rocks has more heavy rocks than the second one, then it is also heavier than another. \textit{Fact 2.} If two sets of 10 rocks have the same number of heavy rocks, then the set with the heaviest rock among light ones (in these two sets) is heavier. \textbf{Proof of the upper bound}. First, we need an auxallary definition: A \textit{switching} of two stones $A$ and $B$ for a weighting of two sets of size 10 is the weighting of these sets after the replacement the stone $A$ by $B$ and the stone $B$ by $A$, i.e. if $A$ and $B$ lie on the same side or do not lie on the pan scales, then we have the same weighting, if only one stone eighther $A$ or $B$ lies on the pan scales, then we just replace this stone by another and do not touch the rest rocks, if the stone $A$ lies on one side and $B$ lies on another, then $A$ and $B$ switch their sides and all the rest rocks lie on the same sides. Let us show that there are at most 171 bad pairs of rocks. For that we need a few facts. \textit{Fact 3.} A pair $\{A, B\}$ of two rocks is bad iff the result of any weighting with $A$ replaced by $B$ and $B$ replaced by $A$ is the same. See the proof of Fact 3 below. \textit{Fact 4.} If the pairs $\{X, Y\}$ and $\{X, Z\}$ are bad, then the pair $\{Y, Z\}$ is also bad. Proof. Consider a sequence of weightings: any weighting $\omega_1$, the switching $\omega_2$ of X and Y for $\omega_1$, the switching $\omega_3$ of $Z$ and $X$ for $\omega_2$, and then again the switching $\omega_4$ of $Y$ and $X$ for $\omega_3$. By Fact 3, the results of these weightings are the same. But $\omega_4$ is the switching of $Y$ and $Z$ for $\omega_1$. Indeed: $(X, Y, Z)\to (Y, X, Z) \to (Y, Z, X) \to (X, Z, Y)$ This implies that the result of the switching of $Z$ and $Y$ for any weighting is the same. Thus, by Fact 3, the pair $\{Y, Z \}$ is bad. This completes the proof of the fact. Consider a graph whose vertices are rocks and edges are pairs of bad rocks. By Fact 4, each component of the graph is a complete graph. Claim 5. For any 20 rocks $A_1, A_2,\dots, A_{20}$, among pairs $\{A_1, A_2\}$, $\{A_3, A_4\}, \dots, \{A_{19}, A_{20}\}$ their is at least one clear pair. Proof. Let us weight the following sets of rocks: $\{A_1, A_3,\dots, A_{19}\}$ and $\{A_2,A_4,\dots, A_{20}\}$. If the pan scales shows the equilibrium then after a switching of any pair we easily understand which rock in the pair is heavier. If one set of 10 rocks is heavier than another, then we switch one by one our 10 pairs of rocks. After all changes the result of the last weighting is opposite. It means there is a switching (of some pair $\{A,B\}$) changing the result, and thus the pair $\{A, B\}$ is clear. This finishes the proof of Fact 5. Now consider the largest matching of each component of our graph. Let the size of the matching of $i$-th component is $n_i$. According to Fact 5, the sum of $n_i$ is at most 9. So, in the $i$-th component there is at most $2n_i+1$ vertices, and that why there are at most $n_i(2n_i+1)$ edges. Therefore, \[ \sum n_i(2n_i+1) = 2\sum n_i^2 + \sum n_i \leqslant 2(\sum n_i)^2 + \sum n_i \leqslant 2\cdot 9^2 + 9 = 171. \]Proof of Fact 3. A proof of the sufficient implication is obvious. Thus, let us prove that if the result of the switching of a pair for a weighting is different from the result of the weighting, then this pair is clear. There are several possibilities: each stone of the pair lies on the right side of the pan scales, on the left side or does not lie on the pan scales. If both rocks lie on the same side or do not lie on the pan scales, then the result is the same (since the weighting is the same). If stones are on different side of the scale pan, then there are several possible cases: \begin{itemize} \item[>,=] In this case the rock on the left side is heavier. \item[>,<] In this case the rock on the left side is heavier. \item[=,>] In this case the rock on the right side is heavier. \item[=,<] In this case the rock on the left side is heavier. \item[<,=] In this case the rock on the right side is heavier. \item[<,>] In this case the rock on the right side is heavier. \end{itemize} If one of the stones does not lie on the scale pan, then the weight on one side does not change after the switching. Thus, we easily see which rock of the pair is heavier, and so this pair is clear.