Problem 6. In the showcase of a jewelry store, there are 15 diamonds. Next to them are signs indicating their weights, which are $1, 2, \ldots, 15$ carats. The seller has a balance scale and four weights with masses of $1, 2, 4,$ and 8 carats. The customer is allowed only one type of weighing: place one of the diamonds on one pan of the scale, and the weights on the other pan to verify that the weight indicated on the corresponding sign is correct. However, for each weight taken, the customer must pay the seller 100 coins. If a weight is removed from the scale and does not participate in the next weighing, the seller keeps it. What is the smallest amount that will have to be paid to check the weights of all the diamonds?

$[8$ points]

(A. V. Gribalko)
Answer: 800 coins.

Solution. Example.

| Which weights we buy | What we weigh | How many coins we paid |
| :---: | :--- | :---: |
| 1 | $\mathbf{1 = 1}$ | 100 |
| 2 | $1+2=\mathbf{3}, 2=\mathbf{2}$ | 200 |
| 4 | $2+4=\mathbf{6}$ | 300 |
| 1 | $1+2+\mathbf{4}=\mathbf{7}, 1+\mathbf{4}=\mathbf{5}, \mathbf{4}=\mathbf{4}$ | 400 |
| 8 | $\mathbf{4}+8=\mathbf{12}$ | 500 |
| 1 | $1+\mathbf{4}+8=\mathbf{13}$ | 600 |
| 2 | $1+2+\mathbf{4}+8=\mathbf{15}, 2+\mathbf{4}+8=\mathbf{14}, 2+8=\mathbf{10}$ | 700 |
| 1 | $1+2+8=\mathbf{11}, \mathbf{1}+8=\mathbf{9}, 8=\mathbf{8}$ | 800 |

Estimate. At each weighing, we either buy one or several weights or return them to the seller. Therefore, we have bought and returned a total of $N \geqslant 15$ weights. After the last weighing, we still have at least one weight in our possession, so we bought more than we returned. This means we bought more than half of $N$, i.e., at least 8 weights, and thus paid the greedy seller no less than 800 coins.

Estimate (alternative method). Imagine that the payment for each weight is divided into two parts: 50 coins are paid by the buyer when they take the weight, and another 50 when they return it. If we assume that all weights are returned to the seller at the end, the total payment remains the same under this method of calculation.

Consider 16 moments: the beginning, when the buyer takes the first weights, 14 intervals between weighings, and the end, when the buyer returns the remaining weights. At each of these moments, the buyer performs some action (taking or returning something), so they must pay at least 50 coins, and in total, they will have to pay no less than $50 \cdot 16 = 800$ coins.

Comment. From the solution, it is clear that the optimal order of weighing involves going through all possible sets of weights, with adjacent sets differing by the addition or removal of exactly one weight. Such a sequence of sets is called a Gray code.

Why were Gray codes invented? Imagine that we want to know the position of a rotating disk. If we only need a rough idea, we can paint one half of the disk black and the other half white and place a photodetector. Now we always know which half of the disk is facing the detector.

But suppose we want more precision. We can place several photodetectors and paint several rings on the disk, with each sector labeled with its number in black and white stripes as a binary code (see the left image).
![](https://cdn.mathpix.com/cropped/2024_05_06_9c536c324e1528721567g-7.jpg?height=358&width=952&top_left_y=1080&top_left_x=250)

But then, at the boundary between sectors, the detectors might not trigger simultaneously, and between 001 and 010, we might "see" 011 or 000. For such a situation, Gray codes were invented: if only one ring changes color at the boundary of two sectors, we can only get the code of one of these sectors.

Any optimal solution to the problem turns out to be a Gray code for 4 rings and 16 sectors (the Gray code from the solution is used in the right image).