2026年10月26日の解答

答. 最小値は \(\left\lfloor \tfrac{(n-1)^2}{2}\right\rfloor\) である。すなわち \(n=2m\) のとき \(2m(m-1)\)，\(n=2m+1\) のとき \(2m^2\) である。\(n=2026\) のときは \(2050312\) となる。

準備. 最初の \(1\) から最初の \(n\) まで時計回りに並ぶ前半のカードを上のカード，残りを下のカードと呼ぶ。数 \(k\) の \(2\) 枚のカードは残りの \(2n-2\) 枚を \(2\) つの弧に分ける。\(k+1,\dots,n\) の \(2(n-k)\) 枚を含む方を \(k\) の内側の弧，\(1,\dots,k-1\) の \(2(k-1)\) 枚を含む方を外側の弧とよぶ。\(1\) と \(n\) は初めから隣り合っている。

自然な不変量だけでは足りない理由. 各数を \(2\) 枚のカードを結ぶ弦とみなす。\(j\) のカードと \(k\) のカードを入れ替えると，弦 \(j\) と弦 \(k\) が交わるかどうかだけが反転する。初めも終わりもどの \(2\) 本の弦も交わらないので，どの組も偶数回入れ替わる。しかしこれは偶奇の情報にすぎず，本質はどの組が入れ替えを強いられるかを決めることにある。

段階 1：各数はどちらかの弧を空にする. 目標に達する操作列を一つ固定する。同じ数どうしの入れ替えは何も変えないので取り除いてよい。数 \(k\) を固定し，その \(2\) つの弧を追跡する。\(k\) のカードを含まない操作は，\(k\) のカードで隔てられていない隣り合う \(2\) 枚を入れ替えるので，両者は同じ弧にとどまる。\(k\) のカードと \(j\) のカードを入れ替える操作は，その \(j\) のカードを一方の弧から他方へ移す。最後には \(2\) 枚の \(k\) が隣り合うから一方の弧は空であり，弧の枚数の合計は \(2n-2\ge 2\) なので，空になるのはちょうど一方である。最後に空になる弧を \(k\) の側とよぶ（内側または外側）。したがって \(k\) の側が初めに \(j\) のカードを \(2\) 枚とも含むならば，その弧の中の \(j\) の枚数は \(2\) から \(0\) へ変わり，変化は \(j\) と \(k\) の入れ替えによってのみ \(1\) ずつ起こる。ゆえに \(j\) のカードと \(k\) のカードを入れ替える操作は少なくとも \(2\) 回ある。

段階 2：入れ替えを強いられる組を数える. 側が外側の弧である数の集合を \(T\)，\(t=|T|\) とおく。\(j<k\) とする。\(j\) の内側の弧は \(k\) のカードを \(2\) 枚とも含み，\(k\) の外側の弧は \(j\) のカードを \(2\) 枚とも含む。よって \(j\notin T\) または \(k\in T\) ならば，段階 1 より \(j\) と \(k\) の入れ替えは少なくとも \(2\) 回起こる。これを免れるのは \(j\in T\) かつ \(k\notin T\) の場合に限り，そのような組は高々 \(t(n-t)\le \lfloor n^2/4\rfloor\) 個である。各操作が入れ替えるのはちょうど一組の数のカードであるから，異なる組に対する操作は異なり，操作の総数は少なくとも

\[2\left(\binom{n}{2}-\left\lfloor \frac{n^2}{4}\right\rfloor\right)=\left\lfloor \frac{(n-1)^2}{2}\right\rfloor\]

である（\(n=2m\) のとき括弧内は \(m(2m-1)-m^2=m^2-m\)，\(n=2m+1\) のとき \((2m+1)m-m(m+1)=m^2\) である）。

段階 3：等号を達成する構成. \(g=\lfloor n/2\rfloor\) とおく。\(g+1,\dots,n\) は内側の弧を通して，\(1,\dots,g\) は外側の弧を通して閉じる。

内側の組. \(k=n-1,n-2,\dots,g+1\) の順に，上の \(k\) のカードを時計回りに \(1\) 回ずつ動かし，下の \(k\) のカードに隣接させる。\(k\) を扱う時点で \(2\) 枚の \(k\) の間にあるのは，すでに組になった \(k+1,\dots,n\) の \(2(n-k)\) 枚だけであるから，費用は \(2(n-k)\) 回であり，通過された組は通過後に再び隣り合う。合計は \(2(1+2+\dots+(n-g-1))=2\binom{n-g}{2}\) である。これらの操作はすべて \(2\) 枚の \(g\) の間で行われるので，\(1,\dots,g\) の外側の弧は変化しない。

外側の組. \(k=2,3,\dots,g\) の順に，上の \(k\) のカードを反時計回りに動かし，下の \(k\) のカードに隣接させる。その間にあるのはすでに組になった \(1,\dots,k-1\) の \(2(k-1)\) 枚だけであるから，費用は \(2(k-1)\) 回，合計 \(2\binom{g}{2}\) である。

以上ですべての数が組になり，操作回数は

\[2\binom{g}{2}+2\binom{n-g}{2}=n(n-1)-2g(n-g)=2\left(\binom{n}{2}-\left\lfloor \frac{n^2}{4}\right\rfloor\right)\]

であって下界と一致する。段階 2 の言葉では，これは最も均等な分割 \(T=\{1,\dots,g\}\) に対応する。

検証. 初期配置から到達できるすべての配置を幅優先探索し，\(n=2,\dots,8\) に対する最小値 \(0,2,4,8,12,18,24\) を得た。これは \(\lfloor (n-1)^2/2\rfloor\) と一致する。