2023 CMO Problems/Problem 6
Problem
The numbers 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 such that for any two states
and
, it is possible to transform
into a state equivalent to
with at most
operations.
Solution 1
The minimum value of is 2401 .
First, let's prove that .
Consider the number of operations needed to transform the sequence into
. For any three numbers
, 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 edges, meaning at least
operations are needed. Thus,
.
Next, let's prove that , 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 and two different placements
and
, define
as the smaller arc length between the positions of
in the two placements. The points where
are called fixed points, and those where
are called moving points. Denote the number of moving points as
.
We will use mathematical induction to prove that for states and
, at most
operations and rotations are needed to make
and
coincide, inducting on
When , it is evident that
.
Assume the proposition holds for values less than
.
For
, draw a directed edge
from the position of
in
to its position in
.
(1) If there exist two moving points
in
at positions
(without loss of generality, consider clockwise from
to
as a shorter arc) such that the arc
(excluding
and
) contains only fixed points, and
is clockwise and
is counterclockwise, then sequentially swap
, which totals
operations to obtain
. Then
and
differ only by swapping
and
, so
, and
.
Using the induction hypothesis for and
, at most
operations can transform
into
. Thus, at most
operations are needed to transform
into
.
(2) If no such exist, we first prove that all directed edges are in the same direction (without loss of generality, assume all are clockwise).
Assume is clockwise from point
to
. If there exists
starting at
(including point
) that is counterclockwise, choose the closest
to
with its starting point at
. The closest counterclockwise directed edge
starting at
would satisfy the conditions of (1), which is a contradiction.
Hence, all directed edges starting within are clockwise
). Specifically, the directed edge
starting at
is clockwise. Continuing this reasoning, the sequence
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
clockwise by
to obtain
, and
, and
. 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
segments, with
fixed points, then
.
For each segment of fixed points , and the point
preceding
(which is not a fixed point), swap
with
with
with
, totaling
steps, or
steps. Then, rotate clockwise by
to obtain
. Compared to
, the 99-k_\{alpha, \beta\} fixed points remain unchanged, the points at
have moved clockwise by
(for
such points), and the remaining
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)
and
. Using the induction hypothesis for
and
, at most
operations can transform
into
. Therefore, at most
operations can transform
into
.
Returning to the original problem, let be the state obtained by rotating
counterclockwise by
for
. Then:
It follows that there exists such that
. Therefore, at most 2401 operations are needed to transform
into
. Further rotation can then match
to
, proving the proposition.
In summary, the minimum possible value of is 2401 .
~yyx|szm
See Also
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 |