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

是正则的？

第 1/5 步：分析合法对换的确定性规则并检验小情形

n = 1, 2

上一步下一步

通俗地说

整个过程没有任何分支选择：游戏会按照唯一确定的轨迹自动进行，直到 $0$ 落到 $n$ 的紧后方并停下。

a_i = 0 \ (i > 0) \implies a_j = a_{i-1} + 1; \qquad n = 1 \implies (1, 0), \quad n = 2 \implies (1, 2, 0)

详细分析

每当 $a_i = 0$ （ $i > 0$ ）时，合法对换观察紧挨在 $0$ 前面的元素 $a_{i-1}$ ，并将 $0$ 与 $a_j = a_{i-1} + 1$ 交换。因此在任意时刻至多只有一种合法对换可执行，且无法继续对换当且仅当 $0$ 的前一项为 $n$ （或 $i = 0$ ，但由于 $1$ 保持在 $a_0$ 且 $a_{i-1} \ge 1$ ，这不会发生）。对于 $n = 1 = 2^1 - 1$ 和 $n = 2$ ，初始排列 $(1, 0)$ 和 $(1, 2, 0)$ 已经是 $(1, \ldots, n, 0)$ ，故 $n = 1$ 和 $n = 2$ 都是正则的。