Library / /47 of 48

, 2021

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Hong Kong

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?

Solution

Miss Adams needs to perform at least two operations.
A strategy is as follows. In the first operation, she puts the coins of weights $1$ to $15$ on one side, and the three coins of weights $39$ , $40$ and $41$ on the other side.

Then the two groups will be of the same weight ( $120$ ). Since the total weight of $15$ coins is at least $1+2+\cdots+15=120$ and the total weight of $3$ coins is at most $39+40+41=120$ , this is the only situation for which a group of $15$ coins has the same weight as a group of $3$ coins. So Mr. Bean knows the two unused coins are of weight $37$ and $38$ . Miss Adams then puts the $1$ -gram coin and the $37$ -gram coin on one side, and the $38$ -gram coin on the other side. Hence Mr. Bean will know which coin has weight $1$ .
Now we show that one operation is not enough. If one operation is enough, then the $1$ -gram coin should be the only coin in its group (a group on the balance or the unused group).
* If the $1$ -gram coin is put on the balance and the other group on the balance contains more than one coin, the situation is the same if the $1$ -gram coin and the $2$ -gram coin are swapped.
* If the $1$ -gram coin is put on the balance and the other group on the balance contains exactly one coin, the situation is the same if the $1$ -gram coin is replaced by any unused coin.
* If the $1$ -gram coin is the only unused coin and one side of the balance is heavier, then that side has weight at least $158$ as the total weight of all coins is $315$ , while the other side has weight at most $156$ . So the situation is the same if the $1$ -gram coin and the $2$ -gram coin are swapped.
* If the $1$ -gram coin is the only unused coin and the two sides of the balance have the same weight, we call the group containing the $3$ -gram coin group A, and the other group B. If group A contains a coin of weight $k \neq 3$ and group B contains a coin of weight $k+1$ , then we can swap these two coins, and swap the $1$ -gram coin and the $3$ -gram coin. The two groups still have the same weight. In the remaining case, group A should contain the heaviest coins among those with weight $1$ , $2$ , $\ldots$ , $15$ (possibly none), and the heaviest coins among those with weight $37$ , $38$ , $39$ , $40$ , $41$ . But then the total weight of group A cannot be $157$ . The computations are illustrated below.
- $2+3+\cdots+15=119<157$
- $4+5+\cdots+15+41=155<157<158=3+4+\cdots+15+41$
- $10+11+\cdots+15+40+41=156<157<165=9+10+\cdots+15+40+41$
- $14+15+39+40+41=149<157<162=13+14+15+39+40+41$
- $38+39+40+41=158>157$
Therefore, in any case Mr. Bean cannot tell whether the single coin has weight $1$ or not. So at least two operations are needed.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.