2023 CMO Problems/Problem 6

Problem

The numbers $1,2, \ldots, 99$ are placed on the vertices of a given regular 99 -gon, with each number appearing exactly once. This arrangement is called a "state." Two states are considered "equivalent" if one can be obtained from the other by rotating the 99 -gon in the plane.

Define an "operation" as selecting two adjacent vertices of the 99-gon and swapping the numbers at these vertices. Find the smallest positive integer $N$ such that for any two states $\alpha$ and $\beta$ , it is possible to transform $\alpha$ into a state equivalent to $\beta$ with at most $N$ operations.

Solution 1

The minimum value of $n$ is 2401 .

First, let's prove that $n \geqslant 2401$ .

Consider the number of operations needed to transform the sequence $1,2,3, \ldots, 99$ into $99,98, \ldots, 1$ . For any three numbers $a, b, c$ , if none of the pairs have been operated on, their order cannot change and it is impossible to achieve the latter sequence.

Therefore, among any three numbers, at least two must have undergone an operation. This can be converted into a graph theory model: represent the 99 numbers as 99 vertices, and if two numbers have not been operated on, draw an edge between the corresponding vertices. From the above, we know that the graph contains no triangles. By Turán's theorem, such a graph can contain at most $49 \times 50$ edges, meaning at least $C_{99}^2-49 \times 50=2401$ operations are needed. Thus, $n \geqslant 2401$ .

Next, let's prove that $n \leqslant 2401$ , i.e., at most 2401 operations are sufficient to complete the transformation.

Place the 99 vertices of the regular 99-gon on a circle, with an arc length of 1 between adjacent vertices. For $1 \leqslant i \leqslant 99$ and two different placements $\alpha$ and $\beta$ , define $d_i(\alpha, \beta)$ as the smaller arc length between the positions of $i$ in the two placements. The points where $d_i(\alpha, \beta)=0$ are called fixed points, and those where $d_i(\alpha, \beta) \neq 0$ are called moving points. Denote the number of moving points as $k_{\alpha, \beta}$ .

We will use mathematical induction to prove that for states $\alpha$ and $\beta$ , at most $\sum_{i=1}^{99} d_i(\alpha, \beta)-\frac{1}{2} k_{\alpha, \beta}$ operations and rotations are needed to make $\alpha$ and $\beta$ coincide, inducting on $S(\alpha, \beta)=\sum_{i=1}^{99} d_i(\alpha, \beta)$

When $S(\alpha, \beta)=0$ , it is evident that $\alpha=\beta$ . Assume the proposition holds for values less than $S(\alpha, \beta)$ . For $1 \leqslant i \leqslant 99$ , draw a directed edge $l_i$ from the position of $i$ in $\alpha$ to its position in $\beta$ . (1) If there exist two moving points $i, j$ in $\alpha$ at positions $u, v$ (without loss of generality, consider clockwise from $u$ to $v$ as a shorter arc) such that the arc $\overset{\frown}{uv}$ (excluding $u$ and $v$ ) contains only fixed points, and $l_i$ is clockwise and $l_j$ is counterclockwise, then sequentially swap $\left(u, w_1\right),\left(w_1, w_2\right),\left(w_2, w_3\right), \ldots,\left(w_{t-1}, w_t\right),\left(w_t, v\right),\left(w_{t-1}, w_t\right), \ldots,\left(w_2, w_3\right),\left(w_1, w_2\right),\left(u, w_1\right)$ , which totals $2 t+1$ operations to obtain $\alpha^{\prime}$ . Then $\alpha$ and $\alpha^{\prime}$ differ only by swapping $u$ and $v$ , so $k_{\alpha^{\prime}, \beta} \geqslant k_{\alpha, \beta}-2$ , and $S\left(\alpha^{\prime}, \beta\right)=S(\alpha, \beta)-2(t+1)$ .

Using the induction hypothesis for $\alpha^{\prime}$ and $\beta$ , at most $S\left(\alpha^{\prime}, \beta\right)-\frac{1}{2} k_{\alpha^{\prime}, \beta} \leqslant S(\alpha, \beta)-$ $\frac{1}{2} k_{\alpha, \beta}-(2 t+1)$ operations can transform $\alpha^{\prime}$ into $\beta$ . Thus, at most $S(\alpha, \beta)-\frac{1}{2} k_{\alpha, \beta}$ operations are needed to transform $\alpha$ into $\beta$ .

(2) If no such $i, j$ exist, we first prove that all directed edges are in the same direction (without loss of generality, assume all are clockwise).

Assume $l_{i_1}$ is clockwise from point $u$ to $v$ . If there exists $l_j$ starting at $\overset{\frown}{w v}$ (including point $v$ ) that is counterclockwise, choose the closest $l_{j_2}$ to $u$ with its starting point at $w$ . The closest counterclockwise directed edge $l_{j_1}$ starting at $w$ would satisfy the conditions of (1), which is a contradiction.

Hence, all directed edges starting within $\widehat{u v}$ are clockwise $\left(^*\right.$ ). Specifically, the directed edge $l_{i_2}$ starting at $v$ is clockwise. Continuing this reasoning, the sequence $l_{i_1}, l_{i_2}, \ldots$ forms a chain of clockwise directed edges, covering the circle, implying that all directed edges are clockwise. (i) If there are no fixed points, rotate $\alpha$ clockwise by $\frac{2 \pi}{99}$ to obtain $\alpha^{\prime}$ , and $S\left(\alpha^{\prime}, \beta\right) \leqslant$ $S(\alpha, \beta)-99$ , and $k_{\alpha^{\prime}, \beta} \geqslant k_{\alpha, \beta}-99$ . By induction hypothesis, the conclusion holds. (ii) If there are fixed points, call a sequence of fixed points a segment of fixed points. Assume there are $t$ segments, with $a_1, \cdots, a_t$ fixed points, then $a_1+\cdots+a_t=99-k_{\alpha, \beta}$ .

For each segment of fixed points $u_1, u_2, \cdots, u_{a_i}$ , and the point $u_0$ preceding $u_1$ (which is not a fixed point), swap $u_0$ with $u_1, u_1$ with $u_2, \cdots, u_{a_i-1}$ with $u_{a_i}$ , totaling $a_i$ steps, or $a_1+$ $\cdots+a_t=99-k_{\alpha, \beta}$ steps. Then, rotate clockwise by $\frac{2 \pi}{99}$ to obtain $\alpha^{\prime}$ . Compared to $\alpha$ , the 99-k_\{alpha, \beta\} fixed points remain unchanged, the points at $u_0$ have moved clockwise by $a_i+1$ (for $t$ such points), and the remaining $k_{\alpha, \beta}-t$ points have moved clockwise by 1 . Thus:

\[S\left(\alpha^{\prime}, \beta\right) & =S(\alpha, \beta)-\sum_{i=1}^t\left(a_i+1\right)-\left(k_{\alpha, \beta}-t\right)\] (Error compiling LaTeX. Unknown error_msg)

$=S(\alpha, \beta)-\left(99-k_{\alpha, \beta}+t\right)-\left(k_{\alpha, \beta}-t\right) \\$ $=S(\alpha, \beta)-99$ and $k_{\alpha^{\prime}, \beta} \geqslant 0$ . Using the induction hypothesis for $\alpha^{\prime}$ and $\beta$ , at most $S(\alpha, \beta)-99$ operations can transform $\alpha^{\prime}$ into $\beta$ . Therefore, at most $S(\alpha, \beta)-99+99-k_{\alpha, \beta} \leqslant$ $S(\alpha, \beta)-\frac{1}{2} k_{\alpha, \beta}$ operations can transform $\alpha$ into $\beta$ .

Returning to the original problem, let $\beta_i$ be the state obtained by rotating $\beta$ counterclockwise by $\frac{2 i \pi}{99}$ for $0 \leqslant i \leqslant 98$ . Then: $\sum_{i=0}^{98}\left(S\left(\alpha, \beta_i\right)-\frac{1}{2} k_{\alpha, \beta_i}\right)=\sum_{i=0}^{98}\left(\sum_{j=1}^{99} d_j\left(\alpha, \beta_i\right)-\frac{1}{2} k_{\alpha, \beta_i}\right)=99 \cdot 49^2$

It follows that there exists $i$ such that $S\left(\alpha, \beta_i\right)-\frac{1}{2} k_{\alpha, \beta_i} \leqslant 49^2=2401$ . Therefore, at most 2401 operations are needed to transform $\alpha$ into $\beta_i$ . Further rotation can then match $\beta_i$ to $\beta$ , proving the proposition.

In summary, the minimum possible value of $n$ is 2401 . ~yyx|szm

2023 CMO(CHINA) (Problems • Resources)
Preceded by Problem 5	Followed by Last Problem
1 • 2 • 3 • 4 • 5 • 6
All CMO(CHINA) Problems and Solutions

Page

Toolbox

Search

2023 CMO Problems/Problem 6

Problem

Solution 1

See Also