Problem 9.6. (20 points) There were $n$ identical-looking coins weighing $x_{1}, x_{2}, \ldots, x_{n}$ grams (the weights of the coins are pairwise distinct positive real numbers), and also weightless stickers with numbers $x_{1}, x_{2}, \ldots, x_{n}$. At night, a lab assistant weighed the coins and labeled them with stickers. It is required to check using a balance scale that he did not mix anything up. For example, if $n=6, x_{1}=1, \ldots, x_{6}=6$, then this can be done in 2 weighings, verifying that

$$
\begin{aligned}
& 1+2+3=6 \\
& 1+6<3+5
\end{aligned}
$$

Does there exist for $n=8$ a set of weights $x_{1}, x_{2}, \ldots, x_{8}$, the correct labeling of which can be verified in 2 weighings?
Answer: 2 yes

Solution. Consider the weights 10, 20, 25, 30, 35, 201, 203, 207 (weights will be measured in grams hereafter). We will perform two checks:

$$
\begin{aligned}
10+20+30 & =25+35 \\
10+25+201 & <30+207
\end{aligned}
$$

First, consider the first weighing. We will prove that if some three coins balance some two coins, then these must be 10, 20, 30 on one side and 25, 35 on the other.

We will call the coins 10, 20, 25, 30, 35 small, and the coins 201, 203, 207 - large.

If among the five coins participating in the first weighing there are large ones, then on each side there must be exactly one such coin (otherwise, the side with more such coins would outweigh). At the same time, the weights of all small coins are divisible by 5, while the weights of large coins give different remainders when divided by 5. Then the total weights on the sides give different remainders when divided by 5, which is impossible in the case of equality.

Therefore, all five coins are small. Then each side weighs $\frac{1}{2}(10+20+25+30+35)=$ $=60$. It is easy to understand that the sum of the weights of two coins can be 60 only if these two coins weigh 25 and 35. Then the other three coins weigh 10, $20,30$.

Thus, if the first weighing shows equality, then 10, 20, 30 are on the side with 3 coins (this group will be called $A$), and 25, 35 - on the side with two coins (this group will be called $B$). At the same time, the coins 201, 203, 207 (this group will be called $C$) do not participate in the first weighing.

Now consider the second weighing. On one side, one coin from each of the three groups $A, B, C$ is taken, the minimum sum of the weights of such coins is $10+25+201=236$. On the other side, one coin from groups $A$ and $C$ is taken, the maximum sum of the weights of such coins is $30+$ $207=237$. Given that 237 is only 1 more than 236, the inequality in the second weighing will not hold for any other coins. Therefore, on one side lie the coins $10,25,201$, and on the other - $30,207$.

Thus, in each weighing, we uniquely determined the set of coins on each side. At the same time, for all 8 coins, the pairs of groups they belong to in the first and second weighings (either on the side with 3 coins, or on the side with 2 coins, or not weighed) are different. Therefore, the weight of each coin is uniquely determined.

Remark. In any correct algorithm, one weighing must establish the equality of the weights of two coins on one side with three coins on the other, and the other weighing must establish that two coins on one side are heavier than three coins on the other. This can be understood from the following considerations.

- Coins that are in one of the three groups (on the first side, on the second, or not weighed) in one weighing must end up in different groups in the second weighing. (Indeed, if two coins ended up in the same groups in both weighings, the lab assistant could mix them up and we would not notice.)
- From the previous point, it follows that no weighing can create a group of 4 or more coins. This means that in each weighing, there are either 3 coins on each side, or 3 and 2.
- Also from the first point, it follows that the coins can be arranged in a $3 \times 3$ table, with the groups of the first weighing along the rows and the groups of the second weighing along the columns; exactly one cell will remain without a coin.

| $a_{1}$ | $a_{2}$ | $a_{3}$ |
| :--- | :--- | :--- |
| $b_{1}$ | $b_{2}$ | $b_{3}$ |
| $c_{1}$ |  | $c_{3}$ |

- Both weighings cannot have the same format and outcome. (For example, it cannot be that in both weighings 2 coins on one side outweigh 3 coins on the other.) Indeed, in this case, if the rows and columns in the table above are ordered in the same way (for example, in the order light/heavy/unweighed), the empty cell would be on the main diagonal; then the lab assistant could mix up the labels in such a way that the coins would be reflected relative to this diagonal, and we would not notice this.
- There cannot be a weighing in which there are 3 coins on each side, and they balance each other. For example, let the first weighing be set up this way; its sides correspond to the first and second rows of our table. Then the lab assistant could mix up the labels in such a way that the first and second rows would swap places. This would not affect the results of our weighings, that is, we would not notice such an error.
- There cannot be a weighing in which there are 3 coins on each side, and one side is heavier than the other. To prove this, assume the contrary - let this be the first weighing. The lighter side of this weighing corresponds to the first row, and the heavier side to the third row; the columns are ordered so that the group of 2 coins from the second weighing is in the last column (regardless of the structure of the second weighing).

| $a_{1}$ | $a_{2}$ | $a_{3}$ |
| :--- | :--- | :--- |
| $b_{1}$ | $b_{2}$ |  |
| $c_{1}$ | $c_{2}$ | $c_{3}$ |

If we now reorder the numbers in the columns from top to bottom in ascending order (leaving the empty cell empty), the weight readings will not change: the composition of the columns will not change, and the bottom row will be heavier than the top row. But if we then swap, for example, the two lower coins in the central column, the bottom row will still be heavier than the top row! It turns out that we cannot uniquely determine the placement of the coins, that is, the lab assistant has a chance to deceive us again.

- Similarly, it can be shown that there cannot be a weighing in which the side with three coins outweighs the side with two.

It is also not difficult to understand from similar considerations that for 9 coins, it is impossible to get by with two weighings in any situation.

## Criteria

The highest suitable criterion is used:

20 points. A correct example of a set of masses and a description of two weighings that allow checking the correctness of the labeling is provided.

3 points. The work contains an indication that coins that end up in the same group during the first weighing must end up in different groups during the second weighing.

3 points. The work provides an example of a set of masses and a description of two weighings that do not allow checking the correctness of the labeling, but coins that end up in the same group during each weighing end up in different groups during the other weighing.