MathLabs

第5問

列 0,1,…,n0, 1, \ldots, n の順列 (a0,a1,…,an)(a_0, a_1, \ldots, a_n) が与えられている。aia_i と aja_j の互換は、i>0i > 0 に対して ai=0a_i = 0 であり、かつ ai−1+1=aja_{i-1} + 1 = a_j を満たすとき正当（legal）と呼ばれる。順列 (a0,a1,…,an)(a_0, a_1, \ldots, a_n) は、何回かの正当な互換の後に (1,2,…,n,0)(1, 2, \ldots, n, 0) になるとき正則（regular）と呼ばれる。順列 (1,n,n−1,…,3,2,0)(1, n, n-1, \ldots, 3, 2, 0) が正則となるような数 nn をすべて求めよ。
ステップ 2/5: 最初の左移動パスによって偶数 n>2n > 2 をすべて除外する
前のステップ次のステップ
ざっくり言うと

最初のパスで 00 は左へ2マスずつ飛んでいくが、nn が偶数のときはその2マス飛びによって 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 と入れ替わって左へ2つ飛び、次は直前が 44 なので 55 と入れ替わる。n>2n > 2 が偶数のとき、このようにして 3,5,…,n−13, 5, \ldots, n-1 と次々に入れ替わる。ところが n−1n - 1 は a1=na_1 = n の直後の添字 22 の位置にあるため、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) ではない。