On the table there are $20$ coins of weights $1,2,3,\ldots,15,37,38,39,40$ and $41$ grams. They all look alike but their colours are all distinct. Now Miss Adams knows the weight and colour of each coin, but Mr. Bean knows only the weights of the coins. There is also a balance on the table, and each comparison of weights of two groups of coins is called an operation. Miss Adams wants to tell Mr. Bean which coin is the $1$ gram coin by performing some operations. What is the minimum number of operations she needs to perform?
Problem
Source: 2021HKTST1 Q3
Tags: combinatorics, coins, Operations
17.10.2020 16:58
An extremely tedious problem(which costs me and some other IMO 2020 team members $2$ hours during the test). The answer is $2$. We will first describe a "winning strategy" with $2$ operations. Denote Miss Adams and Mr. Bean by $A$ and $B$ respectively. A will first put $$(2,3,...,15,38)\hspace{3pt}\text{and} \hspace{3pt}(37,39,40,41)$$on both sides, afterwards, he will put $$(1,2,37)\hspace{3pt}\text{and}(41)$$on both sides. In $B's$ view, he will see the following: $$a_2+a_3+...+a_{15}+a_{16}=a_{17}+a_{18}+a_{19}+a_{20}$$and $$a_1+a_{2}+a_{17}<a_{20}$$CLAIM. $a_{17},a_{18},a_{19},a_{20}$ are all in the set $\{37,38,39,40,41\}$ Proof. Just a sketch since it is too annoying. Let $C=\{37,38,39,40,41\}$ and $D=\{a_{17},a_{18},a_{19},a_{20}\}$. We can reject the case $|C\cap D|=2$ and $|C\cap D|=3$ based on the value of $a_1$(noticing that $a_1$ must be odd since the total weight of the coins is odd. Each case is just a simple calculation. For example, if $a_1=41$, then $$\frac{315-41}{2}=R.H.S.\leq 15+38+39+40$$which is impossible. $\blacksquare$ Now the only solution to $a_1+a_2+a_{17}<a_{20}$ is $(1,2,37,41)$. Moreover from $a_{1}$ is odd $B$ will know that $a_1=1$. $\blacksquare$ $\noindent\rule{15.5cm}{0.4pt}$ Now we will show that $1$ operation is not sufficient, which is just more annoying(so I will just provide a sketch). CASE I: $1$ is weighted 1. If there are at least two coins on the same side as $1$, then we can't distinguish that coin and $1$, contradiction. 2. Hence $1$ is the only coin in that side, swapping $1$ and $2$ the expression still holds, so we can't distinguish $1$ and $2$, contradiction. CASE II: $1$ is not weighted 1. Firstly if it is an inequality then swapping $1$ with any coin on the weaker side the inequality still holds, so we can't distinguish $1$ and that coin, contradiction. 2a. So it must be an equality. If there are more than one unweighted coin then we can't distinguish between $1$ and that coin, contradiction. 2b. So exactly $19$ coins are weighted. Now let the set of coins in L.H.S. be $X$ and the set of coins in R.H.S. be $Y$. Suppose $3\in X$, we have that if $n\in X$ then $n\in X+1$, otherwise we can swap $1,3$ and swap $n,n+1$, so we can't distinguish between $1$,$3$, contradiction. Similarly we have that $5\in X$, so if $n\in X$ then $n+2\in X$. Now $3,5,6,...,15\in X$, by counting the total weight we have that the other elements in $X$ is $2,4,40$, but this implies $41$ is not in $X$, contradiction. This completes the proof of every case and we are done.