第5問

列

0, 1, \ldots, n

の順列

(a_0, a_1, \ldots, a_n)

が与えられている。

a_i

と

a_j

の互換は、

i > 0

に対して

a_i = 0

であり、かつ

a_{i-1} + 1 = a_j

を満たすとき正当（legal）と呼ばれる。順列

(a_0, a_1, \ldots, a_n)

は、何回かの正当な互換の後に

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

になるとき正則（regular）と呼ばれる。順列

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

が正則となるような数

n

をすべて求めよ。

ステップ 4/5: 帰納的な遷移

P_r \to P_{r+1}

を示し、

n = 2^k - 1

が正則であることを導く

前のステップ次のステップ

ざっくり言うと

$P_r \to P_{r+1}$ の遷移はその場でのマージソートのようなものである。 $R$ 回の左移動パスによって1つおきの長さ $R$ のブロックから要素を1つずつ剥がし、隣のブロックに継ぎ足して長さ $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$ と次々に入れ替わる。1回のパスごとに先頭ブロック $[1 : R+u-1]$ の末尾に $R+u$ が加わり、各奇数番目ブロックの先頭要素が直前の偶数番目ブロックの末尾へ移って、奇数番目ブロックの長さが $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)$ に到達する。