5東京大学 2025年 数学 第5問解答・解説

(1) $A_1,A_2>2$ と仮定する。最初の $T_1$ の後、左端の札は $\displaystyle \min(A_1,A_2)\ge3$ である。その後の順方向の $T_2,\ldots,T_{n-1}$ と逆方向の $T_{n-1},\ldots,T_2$ は左端に触れない。最後の $T_1$ が交換しなければ左端に3以上の札が残り、交換すれば交換前の左端の札が2番目に移る。どちらも最終状態の先頭が $1,2$ になることはない。矛盾であるから、$A_1,A_2$ の少なくとも一方は2以下である。

(2) 数字の大小関係だけが操作に関係するので、札の値を順序を保ったまま別の集合に置き換えても、長さ $m$ の有効な並び方の個数は $c_m$ である。また、最初の2枚は異なる数字である。

まず $A_1=1$ の場合、最初と最後の $T_1$ は交換せず、残る札には長さ $n-1$ の同じ操作列が働く。したがってこの場合は $c_{n-1}$ 通りである。$A_2=1$ の場合は最初の $T_1$ で1が左端に移り、その後の札 $(A_1,A_3,\ldots,A_n)$ に長さ $n-1$ の操作列が働く。最後の $T_1$ は交換しないので、この場合も $c_{n-1}$ 通りである。

次に $A_1=2,\ A_2>2$ の場合を考える。最初の $T_1$ は交換せず、2が左端に残る。残りの札は $\{1,3,\ldots,n\}$ であり、最後の $T_1$ で1を左端へ移して整列させるには、その直前に残りの札が $(1,3,\ldots,n)$ の順になっていなければならない。よって残りの初期順は、札の値を順序を保って読み替えた長さ $n-1$ の有効な並び方であり、ただし先頭に1が来るものは除く。先頭が1の有効な並び方では、その1は左端にとどまり、後ろの $n-2$ 枚が同じ操作列で整列する必要十分条件を満たすため、除かれる数は $c_{n-2}$。この場合は $c_{n-1}-c_{n-2}$ 通りである。

$A_2=2,\ A_1>2$ の場合、最初の $T_1$ で2が左端に移り、残りの札の初期順は $(A_1,A_3,\ldots,A_n)$ となる。最後の $T_1$ で整列させるには残りの札が直前に $(1,3,\ldots,n)$ の順である必要があり、初期の残りの札の先頭は1ではない。したがってこの場合も $c_{n-1}-c_{n-2}$ 通りである。

(1)と札の重複がないことから、以上の4場合 $A_1=1$、$A_2=1$、$A_1=2,\ A_2>2$、$A_2=2,\ A_1>2$ は互いに重ならず、すべての場合を尽くす。ゆえに、$n\ge4$ で $$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}.$$