トップ› 東京大学› 2025年› 理系第5問

東京大学 2025年理系第5問解説

方針・初手

与えられた操作は、いわゆるバブルソートの1パス（隣接互換による走査）に相当する。前半の操作 $(T_1), \dots, (T_{n-1})$ は左から右への走査であり、大きな数を右へ送る働きを持つ。後半の操作 $(T_{n-1}), \dots, (T_1)$ は右から左への走査であり、小さな数を左へ送る働きを持つ。

最終的に完全にソートされるためには、前半の操作を終えた時点での札の並びがどのような条件を満たさなければならないかを明らかにするのが初手である。それぞれの走査において、1回のパスで各要素が左右にどれだけ移動できるかに着目する。

解法1

(1)

前半の操作を終えた直後の札の数字の並びを $B_1, B_2, \dots, B_n$ とする。後半の操作 $(T_{n-1}), \dots, (T_1)$ によって、配列 $B$ は $1, 2, \dots, n$ と昇順にソートされる。

後半の操作において、ある要素が右に移動するのは「左隣にある自身より大きな数と入れ替わるとき」のみである。操作は $T_{n-1}$ から $T_1$ へと降順（右から左）に行われる。一度右へ移動した（位置 $k$ から $k+1$ に移った）要素は、次に比較される操作が $T_{k-1}$ であるため、もはや比較の対象にならず、それ以上右へ移動することはない。したがって、後半の操作において各要素は右へは高々1つしか移動できない。

要素 $B_k$ は現在 $k$ 番目にあり、最終的なソート結果によって値 $B_k$ の位置（$B_k$ 番目）に移動する。右へは高々1つしか移動できないため、最終位置は元の位置 $k$ から見て右に1つまで、すなわち $k+1$ 以下でなければならない。よって、すべての $k \ (1 \le k \le n)$ について次の条件が成り立つ。

$$ B_k \le k+1 $$

次に、前半の操作 $(T_1), \dots, (T_{n-1})$ を考える。この操作では、逆に左から右へ走査が行われるため、ある要素が左に移動するのは「右隣にある自身より小さな数と入れ替わるとき」のみである。一度左へ移動した要素は、すでに通り過ぎた位置の比較となるため、再び比較されることはない。したがって、前半の操作において各要素は左へは高々1つしか移動できない。

ここで、$A_1 \ge 3$ かつ $A_2 \ge 3$ であると仮定して矛盾を導く（背理法）。この仮定のもとでは、数字の $1$ と $2$ の初期状態での位置はどちらも 3 番目以降である。前半の操作で各要素は左へは高々1つしか移動できないため、操作後の配列 $B$ において、$1$ と $2$ の位置はどちらも 2 番目以降となる。これはつまり、$B_1$ が $1$ でも $2$ でもないことを意味し、すなわち $B_1 \ge 3$ である。しかし、先ほど導いたソートされるための必要条件 $B_k \le k+1$ において $k=1$ とすると、

$$ B_1 \le 2 $$

でなければならず、これは $B_1 \ge 3$ と矛盾する。したがって、$A_1$ と $A_2$ のうち少なくとも一方は2以下である。（証明終）

(2)

前半の操作 $(T_1), \dots, (T_{n-1})$ の過程を具体的に追うと、各ステップ $k$ において、これまでの最大値と $A_{k+1}$ が比較され、小さい方が位置 $k$ に残される。すなわち、前半の操作後の配列 $B$ の第 $k$ 項は以下のように表せる。

$$ B_k = \min(\max(A_1, A_2, \dots, A_k), A_{k+1}) \quad (1 \le k \le n-1) $$

(1)より、最終的にソートされるための条件は、すべての $k \ (1 \le k \le n-1)$ に対して $B_k \le k+1$ が成り立つことである。（$k=n$ のときは $B_n \le n+1$ となり常に満たされる）この条件は「$A_1, \dots, A_k$ の最大値と $A_{k+1}$ のうち小さい方が $k+1$ 以下である」ということだから、言い換えると**「集合 $\{A_1, A_2, \dots, A_{k+1}\}$ の中に $k+2$ 以上の数が2つ以上存在してはならない」**と同値である。この条件を満たすような $1, \dots, n$ の順列の総数 $c_n$ を求める。

最後尾の要素 $A_n$ の値によって場合分けを行う。

(i)

$A_n = n$ のとき残りの $n-1$ 個の要素 $A_1, \dots, A_{n-1}$ は $1, \dots, n-1$ の順列である。$n$ はすでに $A_n$ に配置されているため、$k \le n-2$ に対する条件は $n-1$ 個の要素の順列に対する条件と全く同じになる。したがって、この並び方の総数は $c_{n-1}$ 通りである。

(ii)

$A_n = n-1$ のとき $A_1, \dots, A_{n-1}$ は $1, \dots, n-2, n$ の順列である。ここで $n$ を $n-1$ とみなし（リネームし）て考えると、$k \le n-2$ に対する条件「$k+2$ 以上の数が高々1つ」という性質は変わらない。したがって、これも条件を満たす $n-1$ 個の順列と1対1に対応し、並び方の総数は $c_{n-1}$ 通りである。

(iii)

$A_n \le n-2$ のとき上の条件を $k=n-3$ について適用すると、「$A_1, \dots, A_{n-2}$ の中に $n-1$ 以上の数（すなわち $n-1$ と $n$）は高々1つしか存在しない」となる。全体で $n-1$ と $n$ は2つあるので、少なくとも一方は $A_{n-1}$ または $A_n$ の位置にならなければならない。いま $A_n \le n-2$ を仮定しているので、$A_{n-1}$ は必ず $n$ または $n-1$ でなければならない。

・$A_{n-1} = n$ のとき順列は $(A_1, \dots, A_{n-2}, n, A_n)$ の形をしている。ここから $n$ を除外した長さ $n-1$ の順列 $A' = (A_1, \dots, A_{n-2}, A_n)$ を考える。$A'$ は $1, \dots, n-1$ の順列であり、元の条件を満たす（すなわち総数 $c_{n-1}$ の集合に属する）。さらに、末尾の要素 $A_n \le n-2$ であるから、$A'$ は「末尾が $n-1$ ではない」順列である。 $n-1$ 要素の条件を満たす順列のうち、末尾が $n-1$ であるものは（i）と同様に $c_{n-2}$ 通りある。したがって、末尾が $n-1$ でないものの総数は $c_{n-1} - c_{n-2}$ 通りである。

・$A_{n-1} = n-1$ のとき順列は $(A_1, \dots, A_{n-2}, n-1, A_n)$ の形をしている。ここから $n-1$ を除外して $n$ を $n-1$ に読み替えると、上と全く同様に「長さ $n-1$ で条件を満たし、かつ末尾が $n-1$ ではない」順列と1対1に対応する。したがって、この並び方の総数も $c_{n-1} - c_{n-2}$ 通りである。

以上（i）, （ii）, （iii）より、求める総数 $c_n$ はこれらを足し合わせたものとなる。

$$ \begin{aligned} c_n &= c_{n-1} + c_{n-1} + (c_{n-1} - c_{n-2}) + (c_{n-1} - c_{n-2}) \\ &= 4c_{n-1} - 2c_{n-2} \end{aligned} $$

解説

バブルソートのアルゴリズム的な性質を数学的に翻訳する良問である。前半の操作が各ステップでの最大値を右へ押し出す操作であるのに対し、後半の操作の逆順走査によって「要素が右にずれることのできる限界」が決まることに気づけるかが鍵となる。 (2)の漸化式を立てる場面では、「大きな数が前方に複数集まってはならない」という条件に言い換えたうえで、末尾の要素のパターンで場合分けをして次元を落とす（$n$ から $n-1$ にする）という、順列の漸化式における定石のアプローチが有効である。