10.9. In the vertices of a regular 100-gon, 100 chips numbered $1, 2, \ldots, 100$ were placed, in exactly that order clockwise. In one move, it is allowed to swap two adjacent chips if their numbers differ by no more than $k$. For what smallest $k$ can a series of such moves result in a configuration where each chip is shifted one position clockwise relative to its initial position?

(S. Berlov)
# Answer: 50.

Solution. Example. The chip 50 is sequentially exchanged 99 times with the next one counterclockwise. We get the required arrangement.

There are several ways to prove the estimate, below we provide two of them.

The first way. Suppose that for some $k<50$ the required arrangement is obtained.

At any moment, we consider the arc from chip 100 to chip 1 clockwise to be painted. Since chips 100 and 1 cannot be swapped in one move, each specific chip $m$ $(2 \leqslant m \leqslant 99)$ could only enter the painted arc or leave the painted arc by swapping with one of the chips 1 or 100.

Since initially and at the end, chip $m$ was not on the painted arc, it made an equal number of entries onto the painted arc and exits from the painted arc. For $m \leqslant 50$, chip $m$ could not swap with chip 100, so it could only enter or exit by swapping with chip 1. Upon entry, chip 1 moves 1 position clockwise, and upon exit, 1 position counterclockwise. We conduct similar reasoning for chips $m \geqslant 51$, which cannot swap with chip 1.

Thus, we obtain that chips 1 and 100 will make an equal number of moves clockwise and counterclockwise, so they will remain in their positions. Contradiction.

The second way. We will count the shifts of the chips relative to their initial position, with a shift clockwise being counted as positive and a shift counterclockwise as negative. Then, when two chips are swapped, +1 is added to the shift of one of them, and -1 to the other. Therefore, the sum of the shifts after the operations will be 0.

We reason by contradiction: suppose that for $k<50$ each chip $i$ is finally shifted one position clockwise, i.e., its shift is $1+100 t_{i}$ (here $t_{i}$ is the integer "number of rotations" clockwise, in particular, if $t_{i}<0$, chip $i$ made $\left|t_{i}\right|$ rotations counterclockwise). Then the total shift of all 100 chips is $100\left(t_{1}+t_{2}+\ldots+t_{100}\right)+100$. Since it must equal 0, we have $t_{1}+t_{2}+\ldots+t_{100}=-1$.

Since $k<50$, chips with numbers $i$ and $j$, where $j \geqslant i+50$, could not swap places, so their shifts at any moment are definitely less than 100 apart, meaning the "number of rotations" $t_{i}$ and $t_{j}$ are equal for $j \geqslant i+50$. Hence, we have $t_{1}=t_{51}$, $t_{2}=t_{52}, \ldots, t_{50}=t_{100}$. Then the sum $t_{1}+t_{2}+\ldots+t_{100}=2\left(t_{1}+\right.$ $\left.+t_{2}+\ldots+t_{50}\right)$ is even, and thus cannot equal -1. Contradiction.

Remark 1. The last reasoning can be modified as follows.

From this, $t_{1}=t_{51}, t_{1}=t_{52}, \ldots, t_{1}=t_{100}, t_{2}=t_{100}, t_{3}=t_{100}$, $\ldots, t_{50}=t_{100}$, thus all $t_{i}$ are equal to $t_{1}$. Then $t_{1}+t_{2}+$ $+\ldots+t_{100}=100 t_{1} \neq-1$.

Remark 2. The proof can be completed by contradiction in another way, replacing the last paragraph of the solution with the following reasoning.

We will paint chips red for which $t_{i} \geqslant 0$, and blue for which $t_{i}<0$. Clearly, at some point, a blue and a red chip must swap, since the difference in their shifts is at least 100. Since $k<50$, the pair of chips 1 and 51 are of the same color, similarly pairs of chips 1 and $52, \ldots, 1$ and 100, 2 and 100, 3 and $100, \ldots, 50$ and $100-$ are of the same color. Thus, all chips are of the same color. We know that $t_{1}+t_{2}+\ldots+t_{100}=-1$, so among the numbers $t_{1}, \ldots, t_{100}$ there are both non-negative and negative ones, i.e., there are both red and blue chips - contradiction.

Comment. Only the correct answer - 0 points.

Points for the example and the estimate are summed.

A correct example is provided - 2 points.

There is a complete proof of the estimate - 5 points.

In the absence of a complete proof of the estimate, the following progress is evaluated (points for progress (1) are not summed with points for progress (2a), (2b), (2c), points for progress (2a), (2b), (2c) are summed):

(1) The idea of tracking the membership of chips to the arc 100-1 (or the relative position of the triplet of chips $1, m, 100)-2$ points.

(2a) shifts are considered and it is shown that the sum of shifts is $0-1$ point.

(2b) in the assumption that the chips are finally shifted 1 position clockwise, an equation for the sum of "number of rotations" is written -1 point.

(2c) it is shown that chips with different "number of rotations" or with "number of rotations" of different signs must have swapped places at some point -1 point.