https://spherical-harmonics.hateblo.jp/entry/Todai/2025/Rika

2025.02.26記

[5] $n$ を2以上の整数とする． $1$ から $n$ までの数字が書かれた札が各1枚ずつ合計 $n$ 枚あり，横一列におかれている． $1$ 以上 $(n-1)$ 以下の整数 $i$ に対して，次の操作 $(\mbox{T}_i)$ を考える．

$(\mbox{T}_i)$ 　左から $i$ 番目の札の数字が，左から $(i+1)$ 番目の札の数字よりも大きければ，これら2枚の札の位置を入れかえる．そうでなければ，札の位置をかえない．

最初の状態において札の数字は左から $A_1，A_2，\ldots，A_n$ であったとする．この状態から $(n-1)$ 回の操作 $(\mbox{T}_1)$ ， $(\mbox{T}_2)$ ， $\ldots$ ， $(\mbox{T}_{n-1})$ を順に行った後，続けて $(n-1)$ 回の操作 $(\mbox{T}_{n-1})$ ， $\ldots$ ， $(\mbox{T}_{2})$ ， $(\mbox{T}_{1})$ を順に行ったところ，札の数字は左から $1，2，\ldots，n$ と小さい順に並んだ．以下の問いに答えよ．

(1) $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下であることを示せ．

(2) 最初の状態としてありうる札の数字の並び方 $A_1，A_2，\ldots，A_n$ の総数を $c_n$ とする． $n$ が $4$ 以上の整数であるとき， $c_n$ を $c_{n-1}$ と $c_{n-2}$ を用いて表せ．

本問のテーマ

バブルソート

2025.02.26記

[解答]
(1) 最後の $(\mbox{T}_{1})$ で左から $1，2$ と並ぶためには，最後の $(\mbox{T}_{1})$ を行う前の時点で左端が $1$ または $2$ でなければならず，そのためには最初の $(\mbox{T}_{1})$ を行なった時点で左端が $1$ または $2$ である必要があり，よって $A_1$ または $A_2$ のいずれかに $1$ または $2$ がなければならない．

よって $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下である．

(2) (a) $\{A_1，A_2\}=\{1，2\}$ のとき：最初の $(\mbox{T}_{1})$ ， $(\mbox{T}_{2})$ の後，それぞれ $3\sim n$ の並び替えの $c_{n-2}$ 通りあるので $2c_{n-2}$ 通り．

(b) $\{A_1，A_2\}=\{1，k\}$ （ $k\neq 2$ ）のとき：最初の $(\mbox{T}_{1})$ の後，それぞれ $2\sim n$ の並び替えとなるが， $A_2=2$ の場合の $c_{n-2}$ 通りを除くので $c_{n-1}-c_{n-2}$ 通りとなり，この場合は $2c_{n-1}-2c_{n-2}$ 通り．

(c) $\{A_1，A_2\}=\{2，k\}$ （ $k\neq 1$ ）のとき：最初の $(\mbox{T}_{1})$ の後，それぞれ $1，3\sim n$ の並び替えとなるが， $A_2=1$ の場合の $c_{n-2}$ 通りを除くので $c_{n-1}-c_{n-2}$ 通りとなり，この場合も $2c_{n-1}-2c_{n-2}$ 通り．

以上から $c_n=4c_{n-1}-2c_{n-2}$ となる．

$\{A_1，A_2\}=\{1，k\}$ のとき最初の $(\mbox{T}_{1})$ の後は必ず $1，k$ と並ぶので $2c_{n-1}$ 通りであるが，
$\{A_1，A_2\}=\{2，k\}$ のとき最初の $(\mbox{T}_{1})$ の後は $2，k$ と並ぶのは $k\neq 1$ のときであり， $k=1$ となる場合を除かないといけないので $2c_{n-1}$ 通りから $\{A_1，A_2\}=\{1，k\}$ のときの $2c_{n-2}$ 通りを除かなければいけないので， $2\times 2c_{n-1}-2c_{n-2}$ と計算する方がわかり易いかも．

早稲田の理工の完全順列を問いた後に東大を受けるとラッキーだったかも．とは言え，最初(b)の $2\sim n$ の並び替えで(a)と重複するものを除き忘れてた（(c)も同様）．

2025.02.27記
札の並べ替えの方法は「バブルソート」のやり方であるから，「情報」に関する出題だと見ることもできる．この往路のソート $(\mbox{T}_{1})$ 〜 $(\mbox{T}_{n-1})$ によって「右端が $A_1\sim A_n$ の最大値」になり，復路のソート $(\mbox{T}_{n-1})$ 〜 $(\mbox{T}_{1})$ によって「左端が $A_1\sim A_n$ の最小値」になる．

[大人の解答]
この入れ換えはバブルソートの考え方に基づいており，往路の操作 $(\mbox{T}_{i})$ 〜 $(\mbox{T}_{n-1})$ によって右端は $\max\{A_i，…，A_n\}$ となり，引き続き行う復路の操作 $(\mbox{T}_{n-1})$ 〜 $(\mbox{T}_{i})$ によって左端は $\min\{A_i，…，A_n\}$ となる．

(1) 往路の操作 $(\mbox{T}_{1})$ によって左から2番目には札 $\max\{A_1，A_2\}$ が並び，その後の往路の操作 $(\mbox{T}_{2})$ 〜 $(\mbox{T}_{n-1})$ ，及び復路の操作 $(\mbox{T}_{n-1})$ 〜 $(\mbox{T}_{2})$ によって左から2番目の数字は $\min\{\max\{A_1，A_2\}，A_3，…，A_n\}$ となる．

よって復路の最後の操作 $(\mbox{T}_{1})$ は $\min\{A_1，A_2\}$ と $\min\{\max\{A_1，A_2\}，A_3，…，A_n\}$ の比較で，その結果左端の2札の並び $1，2$ となるのだから $\min\{A_1，A_2\}$ は $1$ か $2$ のいずれかである．よって $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下である．

(2) (i) $\min\{A_1，A_2\}=1$ のとき：往路の操作 $(\mbox{T}_{1})$ によって左端が1となり，その後の往路の操作 $(\mbox{T}_{2})$ 〜 $(\mbox{T}_{n-1})$ ，及び復路の操作 $(\mbox{T}_{n-1})$ 〜 $(\mbox{T}_{2})$ は $2\sim n$ の並べ替えだから $A_1=1$ ， $A_2=1$ の場合，それぞれ $c_{n-1}$ 通りあるので合計 $2c_{n-1}$ 通りある．

(i) $\min\{A_1，A_2\}=2$ のとき：往路の操作 $(\mbox{T}_{1})$ によって左端が2となり，その隣りは1とは異なるので，その後の往路の操作 $(\mbox{T}_{2})$ 〜 $(\mbox{T}_{n-1})$ ，及び復路の操作 $(\mbox{T}_{n-1})$ 〜 $(\mbox{T}_{2})$ は $1，3\sim n$ の並べ替えのうち先頭が1となるものを除いたものとなる．ここで先頭が1となるものは往路の操作 $(\mbox{T}_{2})$ で入れ替えが起こらず，，その後の往路の操作 $(\mbox{T}_{3})$ 〜 $(\mbox{T}_{n-1})$ ，及び復路の操作 $(\mbox{T}_{n-1})$ 〜 $(\mbox{T}_3)$ で $3\sim n$ の並べ替えとなる $c_{n-2}$ 通りだから，この場合の並べ替えの場合の数は $A_1=2$ ， $A_2=2$ の場合，それぞれ $c_{n-1}-c_{n-2}$ 通りあるので合計 $2(c_{n-1}-c_{n-2})$ 通りある．

以上から $c_n=4c_{n-1}-2c_{n-2}$ となる．

このように情報の問題を数学として出題するのは東大後期や総合科目などで幾度かあったが，今後も毎年ではないだろうが出題されそうである．同じく統計が背景にある出題も検討しているかも知れない，と適当なことを言っておく．