第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

をすべて求めよ。

ステップ 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$ の形ではない場合を考える。このとき整数 $a \ge 1$ 、 $b \ge 1$ を用いて $N = n + 1 = 2^a(2b + 1)$ と表せる。 $2^a \mid N$ であるから、同様の遷移によって $P_0$ から $P_a$ に至り、そこでは $(0)$ の後ろに長さ $2^a$ のブロックが $2b$ 個（ $[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$ は2番目のブロック $[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$ は正の整数）である。