2026年11月2日の解答

一般に \(n\) 個の数で考える。答は \(2^{n-1}-1\) であり，\(n=2026\) では \(2^{2025}-1\) である。並びを \(a_1,\dots,a_n\) と書く。操作とは，\(j>i\) かつ \(a_i=\max(a_i,\dots,a_j)\) をみたす区間 \(a_i,\dots,a_j\) を逆順にすることである。

素朴な量では足りないこと。 操作は \(a_1,\dots,a_{i-1}\) を動かさず，位置 \(i\) に \(a_j<a_i\) を置くので，並びは辞書式順序で真に減少する。これで有限性は示されるが，得られる上界は \(n!-1\) にすぎない。転倒数も役に立たない。たとえば \(5,1,2,3,4\to 4,3,2,1,5\) で転倒数は 4 から 6 に増える。より精密なポテンシャルが必要である。

第1段：ポテンシャル。 各数 \(v\) に対し，\(v\) より右にあって \(v\) より小さい数の個数を \(r(v)\) とおく。\(w(0)=0\)，\(k\ge1\) に対し \(w(k)=2^{k-1}\) と定める。\(w\) は狭義単調増加であり，\(s\ge1\) のとき \(\sum_{q=0}^{m-1}w(s+q)=w(s+m)-w(s)\)，また \(m\ge1\) のとき \(\sum_{q=0}^{m-1}w(q)=w(m)-1\) が成り立つ。\[\Phi=\sum_{v} w\bigl(r(v)\bigr)\] とおく。\(r(v)\le v-1\) であるから \(\Phi\le\sum_{v=2}^{n}2^{v-2}=2^{n-1}-1\) を得る。

第2段：各操作で \(\Phi\) は少なくとも 1 減る。 長さ \(L\ge2\)，先頭が \(M\) である区間への操作を考える。区間の外の数については \(r\) は変わらない。区間より左の数から見て右側にある値の集合は変わらず，区間より右の数は動かないからである。区間内の数 \(v\) に対し，区間より右にある \(v\) より小さい数の個数を \(s(v)\)，区間内で \(v\) の右および左にある \(v\) より小さい数の個数をそれぞれ \(x(v)\)，\(y(v)\) とおく。操作前は \(r(v)=s(v)+x(v)\)，操作後は区間内の左右が入れ替わるので \(r(v)=s(v)+y(v)\) である。

\(M\) については \(x(M)=L-1\)，\(y(M)=0\) であるから，\(s=s(M)\) とおくとその項は \(w(s+L-1)\) から \(w(s)\) に減る。区間内の他の数を値の小さい順に \(v_1<v_2<\dots<v_{L-1}\) と並べる。区間内で \(v_t\) より小さい数はちょうど \(v_1,\dots,v_{t-1}\) であるから \(y(v_t)\le t-1\) である。また \(v_t\) より小さい数は \(M\) より小さいので \(s(v_t)\le s\) である。よって \(v_t\) の新しい項は \(w(s+t-1)\) 以下である。これらの数の操作前の項の和を \(B\ge0\) とおくと \[\Delta\Phi\le\sum_{t=1}^{L-1}w(s+t-1)-\bigl(w(s+L-1)-w(s)\bigr)-B\] を得る。

\(s=0\) のとき，和は \(w(L-1)-1\) に等しいので \(\Delta\Phi\le-1-B\le-1\) である。\(s\ge1\) のとき，和は \(w(s+L-1)-w(s)\) に等しいので \(\Delta\Phi\le-B\) である。\(B\ge1\) ならばこれで終わる。\(B=0\) ならばすべての \(v_t\) について \(s(v_t)=0<s\) であり，新しい項は \(w(t-1)<w(s+t-1)\) 以下となるから上の不等式は真の不等式になり，\(\Delta\Phi<0\) である。\(\Phi\) は整数であるから，いずれの場合も \(\Delta\Phi\le-1\) である。

したがって操作の列は必ず有限で，その長さは \(\Phi(\text{初期状態})\le2^{n-1}-1\) 以下である。

第3段：\(2^{n-1}-1\) 回の操作列。 操作が可能かどうかは関係する数の大小関係のみで決まるので，ある区間の外の数に触れない限り，その区間を独立した並びとみなして整列してよい。長さ \(m\) の減少列を以下の手順で増加列にするときの操作回数を \(f(m)\) とおく。\(n,n-1,\dots,1\) から始める。まず \(n\) を先頭に置いたまま位置 \(2,\dots,n\)（長さ \(n-1\) の減少列）を \(f(n-1)\) 回で整列し，\(n,1,2,\dots,n-1\) を得る。次に全体を逆順にする。\(n\) が先頭にあり最大であるからこれは許される操作であり，\(n-1,\dots,2,1,n\) を得る。最後に位置 \(1,\dots,n-1\) を \(f(n-1)\) 回で整列する。よって \(f(n)=2f(n-1)+1\)，\(f(1)=0\) であり，\(f(n)=2^{n-1}-1\) となる。

結論。 操作は必ず有限回で終わり，操作の回数の最大値は \(2^{2025}-1\) である。さらに \(n\le8\) の計算機探索によれば，任意の初期状態からの最長の操作列の長さはその状態の \(\Phi\) にちょうど等しい。

検証。 \(n\le8\) のすべての並び（最大 40320 通り）を全探索し，すべての操作で \(\Phi\) が少なくとも 1 減ること，各並びからの最長操作列の長さが \(\Phi\) に等しいこと，最大値が \(n=2,\dots,8\) で \(1,3,7,15,31,63,127\) であることを確かめた。さらに上の再帰的構成を \(n=5,10,15\) で実行し，ちょうど \(2^{n-1}-1\) 回の許される操作で増加列に達することを確認した。