第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)

是正则的？

第 4/5 步：证明归纳转移

P_r \to P_{r+1}

从而确立

n = 2^k - 1

为正则数

上一步下一步

通俗地说

可以把 $P_r \to P_{r+1}$ 看作原地归并排序：通过 $R$ 轮左移，把每隔一个的长度为 $R$ 的块中的元素逐一剥离，并拼接到相邻块末尾，合并成长度为 $2R$ 的块。

P_r \xrightarrow{u = 0, 1, \ldots, R-1} P_{r+1} \implies P_k = [1 : 2^k-1], (0) \text{ for } n = 2^k - 1

详细分析

设 $2R \mid N$ 且当前处于 $P_r$ 。依次对 $u = 0, 1, \ldots, R-1$ ，数字 $0$ 位于 $R + u - 1$ 紧后方并执行一轮左移，依次与 $(0)$ 之后各奇数位置块的首元素 $R+u, 3R+u, \ldots, N-R+u$ 交换。每一轮都将 $R+u$ 并入首块 $[1 : R+u-1]$ ，把每个奇数位置块的首元素移到前一个偶数位置块的末尾，使奇数位置块长度减 $1$ 。经过全部 $R$ 轮（ $u = 0, \ldots, R-1$ ）后，奇数位置块消失，偶数位置块长度翻倍为 $2R$ ，从而得到 $P_{r+1}$ 。当 $n = 2^k - 1$ 时， $N = 2^k$ ，由归纳法最终到达 $P_k = [1 : n], (0) = (1, 2, \ldots, n, 0)$ 。