第5题

给定序列

0, 1, \ldots, n

的一个排列

(a_0, a_1, \ldots, a_n)

。如果对

i > 0

有

a_i = 0

，且

a_{i-1} + 1 = a_j

，则将

a_i

与

a_j

的对换称为合法的。如果排列

(a_0, a_1, \ldots, a_n)

经过若干次合法对换后变为

(1, 2, \ldots, n, 0)

，则称该排列是正则的。问对哪些正整数

n

，排列

(1, n, n-1, \ldots, 3, 2, 0)

是正则的？

第 5/5 步：排除非

2^k - 1

形式的奇数

n

并总结最终答案

上一步下一步

通俗地说

一旦块长达到整除 $n + 1$ 的最大 $2$ 的幂，在 $0$ 后面就会剩下偶数个（ $2b$ 个）块，从而重演偶数 $n$ 时的陷阱，使 $0$ 直接落到 $n$ 的紧后方。

n + 1 = 2^a(2b + 1) \ (a, b \ge 1) \implies P_a \longrightarrow ([1 : 2^a-1], \ldots, [N-2^a : N-1], 0, \ldots)

详细分析

最后，设 $n$ 为奇数但不是 $2^k - 1$ 的形式，则可写为 $N = n + 1 = 2^a(2b + 1)$ ，其中整数 $a \ge 1$ 且 $b \ge 1$ 。由于 $2^a \mid N$ ，同样的转移过程会从 $P_0$ 到达 $P_a$ ，此时 $(0)$ 后面跟着 $2b$ 个长度为 $2^a$ 的块： $[N-2^a : N-1], [N-2 \cdot 2^a : N-2^a-1], \ldots, [2^a : 2 \cdot 2^a - 1]$ 。在紧接着的下一轮中， $0$ 依次与 $2^a, 3 \cdot 2^a, \ldots, (2b-1)2^a = N - 2 \cdot 2^a$ 交换。因为 $N - 2 \cdot 2^a$ 是第二个块 $[N - 2 \cdot 2^a : N - 2^a - 1]$ 的首元素，这次交换会把 $0$ 放到第一个块 $[N - 2^a : N - 1]$ 的末元素 $N - 1 = n$ 的紧后方，导致过程在未完成排序时便告终止。综上所述，该排列是正则的当且仅当 $n = 2$ 或 $n = 2^k - 1$ （ $k$ 为正整数）。