Evolton

東京大学 2025年度 前期日程 第2次学力試験理系数学 第5問

nを2以上の整数とする。1からnまでの数字が書かれた札が各1枚ずつ合計n枚あり,横一列におかれている。
1以上(n−1)以下の整数iに対して,次の操作(Ti)を考える。

(Ti) 左からi番目の札の数字が,左から(i+1)番目の札の数字よりも大きければ,
これら2枚の札の位置を入れかえる。そうでなければ,札の位置をかえない。

最初の状態において札の数字は左からA1,A2,⋯ ,Anであったとする。
この状態から(n−1)回の操作(T1),(T2),⋯ ,(Tn−1)を順に行った後,
続けて(n−1)回の操作(Tn−1),⋯ ,(T2),(T1)を順に行ったところ,
札の数字は左から1,2,⋯ ,nと小さい順に並んだ。以下の問いに答えよ。

(1) A1とA2のうち少なくとも一方は2以下であることを示せ。

(2) 最初の状態としてありうる札の数字の並び方A1,A2,⋯ ,Anの総数をcnとする。
nが4以上の整数であるとき,cnをcn−1とcn−2を用いて表せ。

難易度7/ 10計算量5/ 10目安25分

場合の数、数列、論証・証明 状態分類、漸化式の変形、数え上げ、場合分け、誘導利用

方針

操作は隣り合う2枚を昇順にするだけなので,最小の札1がどのように左へ移動するかを追う。(1)では,1が最初から左2枚にないと仮定し,最後の T1 の直前に左端が2でなければならないことを使う。(2)では,よい並びを左2枚の中の1または2の位置で4つに分ける。A1=1,A2=1 はそれぞれ cn−1 通り。残りは A1=2,A2≧3 と A1≧3,A2=2 で,2を除くと「左端が1でない」n−1 枚のよい並びに対応する。

解答

この操作は,隣り合う2枚を見て,左が右より大きいときだけ入れかえる操作である。したがって,数字1は隣の札と比べられるたびに,右から左へは動くが,左から右へ動くことはない。

(1)
数字1が最初に左から m 番目にあるとする。m=1 または m=2 なら,A1,A2 のうち少なくとも一方は1であり,主張は明らかである。

以下,m≧3 とする。このとき最初の操作 T1 では数字1は関係しない。前半の操作 (T1),(T2),…,(Tn−1) では,数字1は操作 Tm−1 のときにだけ1つ左へ移る。その後の前半の操作は,数字1より右側の比較なので,数字1をさらに左へ動かさない。

後半の操作 (Tn−1),…,(T2),(T1) では,数字1は右側から順に比較される中で,1つずつ左へ移る。最終的に並びが 1,2,…,n になるためには,最後の操作 T1 の直前に,左から1番目と2番目が 2,1 の順に並んでいなければならない。最後の T1 でこの2枚が入れかわり,左端から 1,2 となるからである。

ここで,最初の T1 が終わった後から最後の T1 の直前まで,左端の札は操作に関係しない。実際,その間に行われる操作は T2 以上だけであり,左端を動かさない。したがって,最初の T1 の直後の左端の札は,最後の T1 の直前の左端の札と同じであり,それは2である。

いま m≧3 なので,最初の左2枚に数字1はない。最初の T1 の直後の左端は,A1,A2 の小さい方である。これが2であるから,A1 と A2 の少なくとも一方は2である。

以上より,いずれの場合も A1 と A2 のうち少なくとも一方は2以下 である。

(2)
条件を満たす初期配置を「よい並び」と呼ぶ。n≧4 とする。(1)より,よい並びでは左2枚のうち少なくとも一方が1または2である。これを次の4つの場合に分ける。 A1=1 の場合を考える。数字1は最小なので,左端にある限りどの操作でも右へ動かない。したがって残りの n−1 枚が,数字を1ずつ小さく読み替えたときによい並びになればよい。つまり 2,3,…,n を 1,2,…,n−1 に読み替えることで,n−1 枚のよい並びと一対一に対応する。よってこの場合は cn−1 通りである。 A2=1 の場合を考える。このとき最初の操作 T1 で数字1は左端へ移る。その後は左端の1は動かず,残りの n−1 枚に対して,同じ形の前半・後半の操作が行われる。したがって,1を取り除き,残りを1ずつ小さく読み替えることで,やはり n−1 枚のよい並びと一対一に対応する。よってこの場合も cn−1 通りである。

次に,左2枚に1がない場合を考える。(1)より,左2枚のうち一方は2である。 A1=2,A2≧3 の場合,最初の T1 では入れかわりは起こらず,左端の2は最後の T1 の直前まで左端に残る。ここで左端の2を取り除き,残りの数字のうち3以上を1ずつ小さく読み替えると,n−1 枚のよい並びが得られる。このとき,もとの A2 は3以上なので,読み替え後の左端は1ではない。

逆に,左端が1でない n−1 枚のよい並びがあれば,先頭に2を挿入し,もとの数字1はそのまま,2以上の数字を1ずつ大きくすれば,A1=2,A2≧3 のよい並びが得られる。したがってこの場合の個数は,n−1 枚のよい並びのうち左端が1でないものの個数である。 n−1 枚のよい並びのうち左端が1であるものは,その1を取り除いて残りを1ずつ小さく読み替えると,n−2 枚のよい並びと一対一に対応する。よって左端が1でないものは cn−1−cn−2 通りである。 A1≧3,A2=2 の場合も同様である。最初の T1 で2が左端へ移り,その後は直前の場合と同じ構造になる。したがってこの場合も cn−1−cn−2 通りである。

対応の小さい場合の確認として、直接列挙するとc2=2,c3=6,c4=20であり、c4=4c3−2c2=20 と一致する。

以上の4つの場合は互いに重ならず,すべてのよい並びを尽くしている。したがってcn=cn−1+cn−1+(cn−1−cn−2)+(cn−1−cn−2)=4cn−1−2cn−2である。

総評

難度7,計算量5。想定時間は25分前後。操作列そのものはバブルソートに似ているが,ここでは全体の整列過程を追うより,最小の札1と次に小さい札2の位置を追うのが有効である。(1)で左2枚に1または2が必要だと絞り込めると,(2)は4つの初期配置の場合分けになる。難所は「取り除いて読み替える」対応が本当に一対一であることの説明で,特に cn−1−cn−2 が左端1でない並びを数えていることを明記したい。 全順列列挙による c2,c3,c4 の検算も行い、漸化式の符号と係数を確認した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の場合の数の問題で問題集を作る

出典: 東京大学 2025年度 第2次学力試験 数学(理系)公式問題(大学公式の問題PDF(12ページ))。問題文はHTML表示のために再入力・数式組版しています。