2000 APMO 第 5 题

Given a permutation $\left(a_{0}, a_{1}, \ldots, a_{n}\right)$ of the sequence $0,1, \ldots, n$. A transposition of $a_{i}$ with $a_{j}$ is called legal if $a_{i}=0$ for $i>0$, and $a_{i-1}+1=a_{j}$. The permutation $\left(a_{0}, a_{1}, \ldots, a_{n}\right)$ is called regular if after a number of legal transpositions it becomes $(1,2, \ldots, n, 0)$. For which numbers $n$ is the permutation $(1, n, n-1, \ldots, 3,2,0)$ regular?

Answer: $n=2$ and $n=2^{k}-1, k$ positive integer.

给定序列 $0,1, \dots, n$ 的排列 $\left(a_{0}, a_{1}, \ldots, a_{n}\right)$。如果 $a_{i}=0$($i>0$)且 $a_{i-1}+1=a_{j}$，则 $a_{i}$ 与 $a_{j}$ 的转置被称为合法。如果经过多次合法换位后，排列 $\left(a_{0}, a_{1}, \ldots, a_{n}\right)$ 变为 $(1,2, \ldots, n, 0)$，则该排列称为正则排列。对于哪些数字 $n$ 来说，排列 $(1, n, n-1, \ldots, 3,2,0)$ 是正则排列？

答案：$n=2$且$n=2^{k}-1，k$正整数。