MathLabs

第5题

给定序列 0,1,…,n0, 1, \ldots, n 的一个排列 (a0,a1,…,an)(a_0, a_1, \ldots, a_n)。如果对 i>0i > 0 有 ai=0a_i = 0，且 ai−1+1=aja_{i-1} + 1 = a_j，则将 aia_i 与 aja_j 的对换称为合法的。如果排列 (a0,a1,…,an)(a_0, a_1, \ldots, a_n) 经过若干次合法对换后变为 (1,2,…,n,0)(1, 2, \ldots, n, 0)，则称该排列是正则的。问对哪些正整数 nn，排列 (1,n,n−1,…,3,2,0)(1, n, n-1, \ldots, 3, 2, 0) 是正则的？
第 2/5 步：通过第一轮左移排除所有偶数 n>2n > 2
上一步下一步
通俗地说

在第一轮中，00 每次向左跳两格；当 nn 为偶数时，这种两格跳跃恰好把 00 送到 a1=na_1 = n 的紧后方，使其过早卡死。

n>2 even:(1,n,n−1,…,3,2,0)⟶(1,n,0,n−2,n−1,…,2,3)n > 2\text{ even}: (1, n, n-1, \ldots, 3, 2, 0) \longrightarrow (1, n, 0, n-2, n-1, \ldots, 2, 3)
详细分析

设 n≥3n \ge 3。从 (1,n,n−1,…,3,2,0)(1, n, n-1, \ldots, 3, 2, 0) 出发，00 前面是 22，故与 33 交换并向左跳两位；接着它前面是 44，故与 55 交换，依此类推。当 n>2n > 2 为偶数时，它依次与 3,5,…,n−13, 5, \ldots, n-1 交换。由于 n−1n - 1 位于下标 22 处、紧挨在 a1=na_1 = n 之后，将 00 与 n−1n - 1 交换后得到 (1,n,0,n−2,n−1,…,2,3)(1, n, 0, n-2, n-1, \ldots, 2, 3)，此时 00 紧跟在 nn 后面。此后再无合法对换可用，而 n>2n > 2 时这并非 (1,2,…,n,0)(1, 2, \ldots, n, 0)。