Shapovalov A.V.

A jeweler made an open chain from $N>3$ numbered links. A capricious customer demanded to change the order of the links in the chain. Out of spite, she ordered such an open chain that the jeweler would have to open as many links as possible. How many links will the jeweler have to open?
$3 N$ [mountain $\mathbf{4}]$ links (here $[x]$ is the integer part of the number $x$). Note that in each pair of links that were neighbors but are no longer, at least one link must be opened. The same is true for a pair of non-adjacent links that must become neighbors. If the links are divided into groups such that any two links in a group are either adjacent or will become adjacent (but not both together), then no more than one link can remain unopened in each such group. For example, such a group consists of 4 links that in the old chain followed in the order 1-2-3-4, and in the new one should be in the order 2-4-1-3. Other examples: in the old chain 1-2-3, in the new one 1-3 (and 2 is not connected with them), or in the old chain 1-2, and in the new one they are not connected. By mentally dividing the chain into quartets, with a possible remainder of 1, 2, or 3 links, and requiring such an order in which the quartets and the remainder change in the specified manner, the customer will ensure the opening of no fewer than [ $\left.\frac{3 N}{4}\right]$ links (the extra link from the remainder is attached from the other end). On the other hand, by opening every second link in the original chain, the jeweler will mentally divide the second chain into parts where the sum of the links is no less than half of all the links. In each part, no more than half of the links need to be opened, so no fewer than a quarter of the links can remain unopened.

## Answer

## Problem