【解答・解説】東大理系数学2025 第5問

操作 $(\mathrm{T}_2), \cdots , (\mathrm{T}_{n-1})$ で一番左の札の位置は変わらない。

最初の操作 $(\mathrm{T}_1)$ の後，一番左の札の数は $A_1$ か $A_2$ である。この札の数字を特に $A'$ とおく。この札は最後の $(\mathrm{T}_1)$ の操作まで入れ替わることがない。

最終的に札の数は $1,2,\cdots ,n$ と並ぶため， 最後の $(\mathrm{T}_1)$ の操作の前に左から2枚は $1,2$ もしくは $2,1$ の並びになっている必要がある。

どちらの場合であっても $A'$ は $1$ か $2$ である。

よって，$A_1$ と $A_2$ のいずれかは $2$ 以下である。

$A_1, A_2$ が取る数字で場合分けをする。

$c (A_i = j)$ により，最初の状態としてありうる札の数字の並びであって $A_i = j$ を満たす並び方の総数を表す。

$c (A_i = j,A_k = l)$ により，最初の状態としてありうる札の数字の並びであって $A_i = j$，$A_k = l$ を満たす並び方の総数を表す。

求める場合の数は $$\begin{aligned} &c(A_1=1)+c(A_1=2)+c(A_2=1)+c(A_2=2) \\ &- (c(A_1=1,A_2=2)+c(A_1=2,A_2=1)) \end{aligned}$$ である。

$A_1$ の場合分け

• $A_1 = 1$ の場合

最初と最後の操作 $(\mathrm{T}_1)$ で札の移動は起こらない。ゆえに一番左の札を除いた $n-1$ 枚に操作を場合に帰着されるため，$c(A_1 = 1) = c_{n-1}$ である。

• $A_1 = 2$ の場合

最初の操作を行わなくとも最終的に札の数字は $1,2,\cdots , n$ となる。

実際，$A_2 = 1$ の場合，操作 $(\mathrm{T}_2)$ で札は入れ替わらないため，最後の操作で $1$ と $2$ が入れ替わるため，最初の操作の必要はない。一方，$A_2 \neq 1$ の場合，最初の操作で札は入れ替わらない。

最後の操作の直前，札の数字は $2,1,3, \cdots , n$ と並ぶことになるため，$1,3,4,\cdots , n$ の $n-1$ 枚に操作を行う場合に帰着されるため，$c(A_1 = 2) = c_{n-1}$ である。

$A_2$ の場合分け

• $A_2 = 1$ の場合

最初の操作で札が入れ替わる。その後の状態は $A_1 = 1$ の場合と同じであるため，同様に $c(A_2=1) = c_{n-1}$ である。

• $A_2 = 2$ の場合

最初の操作で札が入れ替わった場合，その後の状態は $A_1 = 2$ の場合と同じである。最初の操作で札が入れ替わらない場合，つまり $A_1 = 1,A_2 = 2$ の場合は $A_1 = 2, A_2 = 1$ のときに操作 $(\mathrm{T}_1)$ を行うときと等価であるため，この場合も $A_1=2$ の場合に帰着される。

よって，$c(A_2=1) = c_{n-1}$ である。

$A_1, A_2$ の場合分け

• $A_1 = 1, A_2 = 2$ の場合

操作 $(\mathrm{T}_1), (\mathrm{T}_2)$ で札の移動は起こらない。ゆえに，左から2枚を除いた $n-2$ 枚の場合に帰着されるため，$c(A_1=1,A_2=2) = c_{n-2}$ である。

• $A_1 = 2, A_2 = 1$ の場合

最初の操作 $(\mathrm{T}_1)$ で札が入れ替わるが，最後の操作 $(\mathrm{T}_1)$ と操作 $(\mathrm{T}_2)$ で札の移動は起こらない。

ゆえに，前と同様に左から2枚を除いた $n-2$ 枚の場合に帰着されるため，$c(A_1=2,A_2=1) = c_{n-2}$ である。

以上より $$c_n = 4c_{n-1} - 2c_{n-2}$$