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 をすべて求めよ。
ステップ 1/5: 操作の一意性を確認し、小さい値 n=1,2n = 1, 2 を調べる
前のステップ次のステップ
ざっくり言うと

操作に選択の余地はなく、00 が nn の直後に到達して停止するまで、手順は一意かつ自動的に進行する。

ai=0 (i>0)  ⟹  aj=ai−1+1;n=1  ⟹  (1,0),n=2  ⟹  (1,2,0)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)
詳しい解説

i>0i > 0 で ai=0a_i = 0 のとき、正当な互換は 00 の直前の要素 ai−1a_{i-1} を見て、00 と aj=ai−1+1a_j = a_{i-1} + 1 を入れ替える操作である。したがって各時点で可能な正当な互換は高々1通りしかなく、操作が不可能になるのは 00 の直前が nn であるとき（または i=0i = 0 のときだが、11 が a0a_0 に留まり ai−1≥1a_{i-1} \ge 1 なので起こらない）に限られる。n=1=21−1n = 1 = 2^1 - 1 と n=2n = 2 では初期順列 (1,0)(1, 0)、(1,2,0)(1, 2, 0) がすでに (1,…,n,0)(1, \ldots, n, 0) になっているため、n=1n = 1 と n=2n = 2 はともに正則である。