Chinese Mathematical Olympiad

The smallest $N=2401$.

Let ${\alpha }^{\ast }$ be the state where the numbers $1,2,\dots ,99$ are arranged counterclockwise at the vertices, and ${\beta }^{\ast }$ be the state where $1,2,\dots ,99$ are arranged clockwise on the circle. We prove that it takes at least $2401$ operations to transform ${\alpha }^{\ast }$ into a permutation identical to ${\beta }^{\ast }$.

Assume ${\alpha }^{\ast }$ transforms into a permutation identical to ${\beta }^{\ast }$ after $m$ operations. If a certain operation swaps numbers $a,b$, then draw an edge between $a$ and $b$, thereby obtaining a graph $G$ with $\{1,2,\dots ,99\}$ as the vertex set and $m$ edges (possibly with repetitions). For any three numbers $1\le x<y<z\le 99$, they are in counterclockwise order in ${\alpha }^{\ast }$ and in clockwise order in ${\beta }^{\ast }$. Hence, there must be at least one operation involving two of these numbers, i.e., there is at least one edge among $x,y,z$ in $G$. Therefore, the complement graph $\bar{G}$ of $G$ does not contain a triangle. According to Turán's theorem, the number of edges in $\bar{G}$ does not exceed $49\times 50=2450$, so the number of edges in $G$ is at least $\left(\genfrac{}{}{0ex}{}{99}{2}\right)-2450=2401$, that is, $m\ge 2401$.

Next, we prove that for any two states $\alpha$ and $\beta$, $\alpha$ can be transformed into a state identical to $\beta$ with no more than $2401$ operations. Without loss of generality, assume $\beta ={\beta }^{\ast }$; otherwise, a permutation of the number table can be applied.

For a (linear) arrangement $\pi =(x_1,x_2,\dots ,x_n)$ composed of several different numbers, an ordered pair $(x_i,x_j)$ with $1\le i<j\le n$ and $x_i>x_j$ is called an inversion pair, and let $I(\pi )$ denote the number of inversion pairs in $\pi$. It is easy to see that if $(x_i,x_{i+1})$ is an inversion pair, then swapping $x_i$ with $x_{i+1}$ to get ${\pi }^{\prime }$ results in $I({\pi }^{\prime })=I(\pi )-1$. When $I(\pi )=0$, $\pi$ is in increasing order. Therefore, for any arrangement $\pi$, it can be transformed into an increasing arrangement with exactly $I(\pi )$ operations (by swapping adjacent numbers).

Numbers $1,2,\dots ,50$ are called small numbers, and numbers $51,\dots ,99$ are called large numbers. Consider the number of small numbers among $50$ consecutive vertices in state $\alpha$. There are $99$ ways to take $50$ consecutive vertices, and each small number appears in exactly $50$ of these ways, so the average number of small numbers is $\frac{50\times 50}{99}\in (25,26)$. Therefore, there must be some $50$ consecutive vertices containing no more than $25$ small numbers, and also some $50$ consecutive vertices containing more than $25$ small numbers. Using the discrete intermediate value theorem, it is easy to prove that there exist $50$ consecutive vertices containing exactly $25$ small numbers (and $25$ large numbers).

Arrange $\alpha$ clockwise starting from a certain number as $(a_1,a_2,\dots ,a_{50},b_1,b_2,\dots ,b_{49}{)}_{\text{cyc}}$ (the subscript cyc indicates a cyclic arrangement), such that among $a_1,a_2,\dots ,a_{50}$, there are exactly $25$ small numbers. Let the small numbers in $a_1,a_2,\dots ,a_{50}$ from left to right be $x_1,x_2,\dots ,x_{25}$, and the large numbers from left to right be $y_1,y_2,\dots ,y_{25}$; let the small numbers in $b_1,b_2,\dots ,b_{49}$ from left to right be $z_1,z_2,\dots ,z_{25}$, and the large numbers from left to right be $w_1,w_2,\dots ,w_{24}$. We have the following two schemes:

Scheme one: (1.1) Swap adjacent numbers in $(a_1,a_2,\cdots ,a_{50})$ to move the small numbers to the first $25$ positions. The minimum number of operations required is $s_1$. (1.2) Swap adjacent numbers in $(b_1,b_2,\cdots ,b_{49})$ to move the small numbers to the last $25$ positions. The minimum number of operations required is $s_2$. Now, we obtain the following cyclic arrangement: $$(x_1,x_2,\cdots ,x_{25},y_1,y_2,\cdots ,y_{25},w_1,w_2,\cdots ,w_{24},z_1,z_2,\cdots ,z_{25}{)}_{\text{cyc}}.(\ast )$$ The reason for this particular arrangement will be explained in a lemma later. (1.3) Perform $I({\sigma }_1)$ operations on ${\sigma }_1=(z_1,\cdots ,z_{25},x_1,\cdots ,x_{25})$ to obtain the arrangement $(1,2,\cdots ,50)$. For ${\sigma }_2=(y_1,\cdots ,y_{25},w_1,\cdots ,w_{24})$, perform $I({\sigma }_2)$ operations to obtain $(51,52,\cdots ,99)$. Thus, we achieve a state identical to ${\beta }^{\ast }$, with a total number of operations equal to $s_1+s_2+I({\sigma }_1)+I({\sigma }_2)$.

Scheme two: (2.1) Swap adjacent numbers in $(a_1,a_2,\cdots ,a_{50})$ to move the small numbers to the last $25$ positions. The minimum number of operations required is $s_1^{\prime }$. (2.2) Swap adjacent numbers in $(b_1,b_2,\cdots ,b_{49})$ to move the small numbers to the first $25$ positions. The minimum number of operations required is $s_2^{\prime }$. Now, we obtain the cyclic arrangement $$(y_1,y_2,\cdots ,y_{25},x_1,x_2,\cdots ,x_{25},z_1,z_2,\cdots ,z_{25},w_1,w_2,\cdots ,w_{24}{)}_{\text{cyc}}.(\ast \ast )$$ (2.3) Perform $I({\sigma }_1^{\prime })$ operations on ${\sigma }_1^{\prime }=(x_1,\cdots ,x_{25},z_1,\cdots ,z_{25})$ to obtain the arrangement $(1,2,\cdots ,50)$. For ${\sigma }_2^{\prime }=(w_1,\cdots ,w_{24},y_1,\cdots ,y_{25})$, perform $I({\sigma }_2^{\prime })$ operations to obtain $(51,52,\cdots ,99)$. Thus, we achieve a state identical to ${\beta }^{\ast }$, with a total number of operations equal to $s_1^{\prime }+s_2^{\prime }+I({\sigma }_1^{\prime })+I({\sigma }_2^{\prime })$.

Next, we prove that one of the two schemes must have an operation count not exceeding $2401$.

Lemma: Consider an arrangement of $a$ red numbers and $b$ blue numbers. Let $s$ be the minimum number of operations required to move the red numbers to the front and the blue numbers to the back by swapping adjacent numbers, and let $t$ be the minimum number of operations required for the opposite arrangement. Then $s+t=ab$, and to achieve the minimum number of operations, each operation must involve swapping a red number with a blue number, thereby not changing the order among the red numbers or among the blue numbers.

Proof of the Lemma: Consider the ordered pairs $(x,y)$ in the arrangement, where $x$ is a blue number and $y$ is a red number, with $x$ positioned to the left of $y$. Let the count of such pairs be $S$. After one operation, $S$ decreases by at most $1$ (remains unchanged if two red or two blue numbers are swapped, decreases by $1$ if a blue number is swapped with a red number to its right, and increases by $1$ if a red number is swapped with a blue number to its right). Therefore, by selecting pairs of consecutive blue and red numbers for each operation, it takes exactly $S$ operations to arrange all red numbers to the left and blue numbers to the right, hence the minimum number of operations $s$ equals $S$. Similarly, $t$ is the count of pairs $(z,w)$, where $z$ is a red number and $w$ is a blue number, with $z$ positioned to the left of $w$. Thus, $s+t$ counts each unordered pair of a red and a blue number exactly once, therefore $s+t=ab$.

With the lemma proven, it also explains why after (1.1) and (1.2) we obtain the cyclic arrangement $(\ast )$, and after (2.1) and (2.2) we obtain $(\ast \ast )$.

By the lemma, $s_1+s_1^{\prime }=25\times 25=625$, $s_2+s_2^{\prime }=24\times 25=600$.

Let $\sigma =(x_1,\cdots ,x_{25})$, $\tau =(z_1,\cdots ,z_{25})$, hence ${\sigma }_1=(\tau ,\sigma )$, ${\sigma }_1^{\prime }=(\sigma ,\tau )$. Then $$I({\sigma }_1)+I({\sigma }_1^{\prime })=2I(\tau )+2I(\sigma )+I(\tau ,\sigma )+I(\sigma ,\tau ).$$ Here $I(\tau ,\sigma )$ denotes the number of inversion pairs in ${\sigma }_1$ formed by taking a number from $\tau$ and a number from $\sigma$, and $I(\sigma ,\tau )$ counts the inversion pairs in ${\sigma }_1^{\prime }$ taking a number from $\sigma$ and a number from $\tau$, so $I(\sigma ,\tau )+I(\tau ,\sigma )$ counts every unordered pair formed by taking one number from $\tau$ and one from $\sigma$, amounting to $25^2=625$. Since $I(\sigma )\le \left(\genfrac{}{}{0ex}{}{25}{2}\right)$ and $I(\tau )\le \left(\genfrac{}{}{0ex}{}{25}{2}\right)$, we have $$I({\sigma }_1)+I({\sigma }_1^{\prime })\le 2\left(\genfrac{}{}{0ex}{}{25}{2}\right)+2\left(\genfrac{}{}{0ex}{}{25}{2}\right)+25^2=1825.$$ Similarly, we find $$I({\sigma }_2)+I({\sigma }_2^{\prime })\le 2\left(\genfrac{}{}{0ex}{}{24}{2}\right)+2\left(\genfrac{}{}{0ex}{}{25}{2}\right)+24\times 25=1752.$$ Therefore, $$(s_1+s_2+I({\sigma }_1)+I({\sigma }_2))+(s_1^{\prime }+s_2^{\prime }+I({\sigma }_1^{\prime })+I({\sigma }_2^{\prime }))\le 625+600+1825+1752=4802.$$ By the principle of averages, one of the schemes must have an operation count not exceeding $2401$.

In conclusion, the smallest $N$ sought is $2401$.