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 をすべて求めよ。
ステップ 3/5: ブロック配置 PrP_r を定義し、奇数 nn で P1P_1 に到達することを確認する
前のステップ次のステップ
ざっくり言うと

nn が奇数のときは最初の左移動が a1=na_1 = n まで届き、すべての偶数がその1つ上の奇数とペアになって長さ 22 の整列ブロックが並ぶ。

Pr=[1:R−1],(0),[N−R:N−1],[N−2R:N−R−1],…,[2R:3R−1],[R:2R−1](R=2r, N=n+1)P_r = [1 : R-1], (0), [N-R : N-1], [N-2R : N-R-1], \ldots, [2R : 3R-1], [R : 2R-1] \quad (R = 2^r,\ N = n+1)
詳しい解説

奇数 n≥3n \ge 3 に対して N=n+1N = n + 1、R=2rR = 2^r とおき、連続する昇順ブロックを [a:b]=(a,a+1,…,b)[a : b] = (a, a+1, \ldots, b) と表す。初期順列を P0P_0 とし、2R∣N2R \mid N のとき PrP_r を [1:R−1],(0),[N−R:N−1],[N−2R:N−R−1],…,[2R:3R−1],[R:2R−1][1 : R-1], (0), [N-R : N-1], [N-2R : N-R-1], \ldots, [2R : 3R-1], [R : 2R-1] と定義する。P0P_0 からの最初のパスでは、nn が奇数であるため 00 は 3,5,…,n3, 5, \ldots, n と次々に入れ替わり、11 の直後の添字 11 に到達して、残りの要素はペア [N−2:N−1],[N−4:N−3],…,[2:3][N-2 : N-1], [N-4 : N-3], \ldots, [2 : 3] を形成する。これはまさに P1P_1 である。