I ененоо I.v.

Brothers Petya and Vasya decided to shoot a funny video and post it on the internet. First, they filmed each of them walking from home to school - Vasya walked for 8 minutes, and Petya walked for 5 minutes. Then they came home and sat down at the computer to edit the video: they started Vasya's video from the beginning and Petya's video from the end (in reverse direction) simultaneously; at the moment when both brothers were at the same point on the path in both videos, they spliced Petya's video with Vasya's. The resulting video shows Vasya walking from home to school, and then at some point, he suddenly turns into Petya and walks backward home. What is the duration of the resulting video?
Let's play the resulting video on one monitor and Petia's video in full from the end on the other. Then the monitors will show different things until the brothers meet at one point on the path, and after that, they will show the same thing. Therefore, the durations of these two videos are equal.

![](https://cdn.mathpix.com/cropped/2024_05_06_180c6050e42e6bfd9e50g-07.jpg?height=97&width=803&top_left_y=232&top_left_x=16)

Author: Grribamio A.V.

On the display of a jewelry store, there are 15 diamonds. Next to them are signs indicating their weights, which are 1, 2, ..., 15 carats. The seller has a balance scale and four weights of 1, 2, 4, and 8 carats. A customer is allowed to perform only one type of weighing: place one of the diamonds on one pan of the balance, and the weights on the other, and 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 balance and does not participate in the next weighing, the seller takes it. What is the minimum amount that will have to be paid to check the weights of all the diamonds?

## Solution

## Example.

## Which weights to buy

1

2

4

## 1

8

1

2

1

## What to weigh

 $1=1$ $1+2=3,2=2$$2+4=6$

$1+2+4=7,1+4=5,4=4$

$4+8=12$

$1+4+8=13$

$1+2+4+8=15,2+4+8=14,2+8=10$

$1+2+8=11,1+8=9,8=8$
How many coins we paid

100

200

300

400

500

600

700

800

Estimate. Moving to each weighing, we either buy one or several weights or give them to the seller. Therefore, we have bought and given away a total of $\mathrm{N} \geq 15$ weights. After the last weighing, we still have at least one weight in our possession, so we bought more than we gave away. 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 (another way.) Imagine that the payment for each weight is divided into two parts: 50 coins the buyer pays when taking the weight, and another 50 when giving it back. If we assume that all weights are returned to the seller at the end, the total payment remains unchanged.

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 (takes something or gives something), so they must pay at least 50 coins, and in total, they will have to pay at least $50 \cdot 16=800$ coins.

Comment. From the solution, it is clear that the optimal order of weighing goes through all possible sets of weights, and neighboring sets differ 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 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, and in each sector, write its number with black and white stripes as a binary code (see the left image).

![](https://cdn.mathpix.com/cropped/2024_05_06_180c6050e42e6bfd9e50g-08.jpg?height=757&width=2067&top_left_y=-1&top_left_x=1)

But then, at the boundary of two sectors, the detectors may 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 right image uses the Gray code from the solution of the problem).

## Answer

800 coins.