東京大学 理系 2025年度 第5問 解説
問題編
問題
$n$ を $2$ 以上の整数とする。$1$ から $n$ までの数字が書かれた札が各 1枚ずつ合計 $n$ 枚 あり、横一列におかれている。$1$ 以上 $(n - 1)$ 以下の整数 $i$ に対して、次の操作 $(T_i)$ を考える。
$(T_i)$ 左から $i$ 番目の札の数字が、左から $(i +1)$ 番目の札の数字よりも大きければ、これら2枚の札の位置を入れかえる。そうでなければ、札の位置をかえない。
最初の状態において札の数字は左から $A_1,A_2,\cdots,A_n$ であったとする。この状態から $(n - 1)$ 回の操作 $(T_1),(T_2),\cdots ,(T_{n-1})$ を順に行った後、続けて $(n - 1)$ 回の操作 $(T_{n-1}),\cdots, (T_2), (T_1)$ を順に行ったところ、札の数字は左から $1, 2,\cdots, n$ と小さい順に並んだ。以下の問いに答えよ。
(1) $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下であることを示せ。
(2) 最初の状態としてありうる札の数字の並び方 $A_1, A_2, \cdots ,A_n$ の総数を $c_n$ とする。$n$ が $4$ 以上の整数であるとき、 $c_n$ を $c_{n-1}$ と $c_{n-2}$ を用いて表せ。
考え方
操作の内容は、隣り合う２枚を比べて、「大小」と並んでいたら「小大」に入れ替える、ということです。これをはじめは左端から右端へとやっていき、その後は右端から左端にやっていく、ということです。
具体的には、最初の状態が次のようになっていたとしましょう。
43152
左から1番目（4です）と2番目（3です）を比べると、「大小」となっているので、入れ替えて「小大」にします。
34152
次に、左から2番目（4です）と3番目（1です）を比べると、「大小」となっているので、また入れ替えます。
31452
次は、左から3番目と4番目の比較ですが、今回は4と5なので、もともと「小大」になっています。こういう場合は何もしません。
31452
最後に（といっても前半の、ですが）、4番目と5番目を比較して、入れ替えをします。
31425
こうして、前半が終了です。今度はこれを右から左へとやっていきます。4番目と5番目を比較すると、2と5なので、入れ替える必要はありません。3番目と4番目は、4と2なので、入れ替えが発生します。
31245
2番目と3番目（1と2）は入れ替え不要、1番目と2番目（3と1）は入れ替えが発生、となります。
13245
こうして、すべての操作を終えました。このケースでは、小さい順には並んでいません（3と2のとこがダメです）が、最初の状態をうまくすれば、問題文の設定のように小さい順に並ぶようにできます。そういうケースを考えましょう、という問題です。
(1)は、1の動きがわかりやすいので、まずは1がどう動くか考えましょう。次に、2がどのようになっていないといけないか、を考えるとわかりやすいと思います。
(2)は、漸化式を作る問題です。(1)で1と2の動きを見たので、1以外や2以外を考えれば $n-1$ 枚のケース、 1と2を除いて考えれば $n-2$ 枚のケースに関連付けられる、という発想で考えてみましょう。
解答編
問題
$n$ を $2$ 以上の整数とする。$1$ から $n$ までの数字が書かれた札が各 1枚ずつ合計 $n$ 枚 あり、横一列におかれている。$1$ 以上 $(n - 1)$ 以下の整数 $i$ に対して、次の操作 $(T_i)$ を考える。
$(T_i)$ 左から $i$ 番目の札の数字が、左から $(i +1)$ 番目の札の数字よりも大きければ、これら2枚の札の位置を入れかえる。そうでなければ、札の位置をかえない。
最初の状態において札の数字は左から $A_1,A_2,\cdots,A_n$ であったとする。この状態から $(n - 1)$ 回の操作 $(T_1),(T_2),\cdots ,(T_{n-1})$ を順に行った後、続けて $(n - 1)$ 回の操作 $(T_{n-1}),\cdots, (T_2), (T_1)$ を順に行ったところ、札の数字は左から $1, 2,\cdots, n$ と小さい順に並んだ。以下の問いに答えよ。
(1) $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下であることを示せ。
解答
(1)
$n=2$ のときは明らかなので、 $n\geqq 3$ のときを考える。
$A_m=1$ とする。もし $m\geqq 3$ ならば、 $A_1$ か $A_2$ のどちらかが $2$ であることを示せばよい。
はじめの $(n-1)$ 回の操作では、操作 $(T_{m-1})$ で入れ替えが発生し、 $1$ は左から $(m-1)$ 番目の場所に移動する。他の操作では $1$ は動かない。その後の $(n-1)$ 回の操作では、 $(T_{m-2})$ から $(T_1)$ の操作で毎回入れ替えが起こり、 $1$ は左端に移動する。
最後の操作 $(T_1)$ で入れ替えが発生することと、最終的な $2$ の場所が左から2番目であることから、最後の操作 $(T_1)$ の直前には $2$ は左端になければならない。後半の操作の $(T_{n-1}),\cdots, (T_2)$ によって $2$ がはじめて左端に移動することはないので、後半の操作をはじめるときには、 $2$ は左端にある必要がある。
はじめの $(n-1)$ 回の操作では、 $2$ の位置が変わるのは高々1回である。なので、 $A_1=2$ の場合か、 $A_2=2$ の場合のどちらかしかない。
以上から、 $A_1$ と $A_2$ のうち、少なくとも一方は $2$ 以下である。
解説
上の解答と同じように、 $A_m=1$ で $m\geqq 3$ とします。次のようになっていた場合を考えてみます。１の場所だけに注目します。
〇〇〇１〇〇
このとき、前半の操作では、「〇１」は必ず「１〇」へ入れ替えが発生します。１が1番小さい数だから当然です。ただ、１が動くのは1回だけです。比較する対象が右へ右へと進んでいくからです。
〇〇１〇〇〇
後半の操作では、途中から、「〇１」から「１〇」への入れ替えが毎回発生するようになります。「１を左に入れ替え→比較対象を左に移動」を繰り返すからです。そして、最終的に次のようになります。
１〇〇〇〇〇
つまり、最初に１がどこにあっても、左端に１が来ることは確定しています。なので、最終的に小さい順になるには、最後の入れ替えで、２は左端にないといけないということがわかります。
２１〇〇〇〇 （最後の操作をやる直前）
後半の操作で２が動くタイミングは、最後の操作のときしかありません。他の操作では、左端に２が移動するような入れ替えが発生しないからです。ということは、後半の操作をやる直前では、すでに２は左端にないといけません。
前半の操作で２が左端に位置するには、最初の操作で２が左端に移動するか、もともと２が左端にあるか、どちらかしかありません。比較する対象が右へ右へと進んでいくからです。
〇２〇１〇〇 （最初の入れ替えで２が左端に行くパターン）
２〇〇１〇〇 （もともと２が左端にあるパターン）
この流れを清書したものが上の解答です。
解答編 つづき
問題
(2) 最初の状態としてありうる札の数字の並び方 $A_1, A_2, \cdots ,A_n$ の総数を $c_n$ とする。$n$ が $4$ 以上の整数であるとき、 $c_n$ を $c_{n-1}$ と $c_{n-2}$ を用いて表せ。
解答
(2)
$n$ 枚の数字を並べる方法のうち、$(2n-2)$ 回の操作を行うことで小さい順に並ぶものを、「うまくいく並べ方」と呼ぶことにする。
(a) $A_1=1$ の場合
操作 $(T_1)$ で入れ替えは発生しない。 $A_2$ から $A_n$ の数を $1$ ずつ減らすと、 $(n-1)$ 枚を使ったときの「うまくいく並べ方」が得られる。
逆に、 $(n-1)$ 枚を使ったときの「うまくいく並べ方」の各数に $1$ を足し、左端に $1$ を並べれば、この場合の「うまくいく並べ方」が得られる。
よって、この場合の「うまくいく並べ方」の総数は $c_{n-1}$ 通り。
(b) $A_2=1$ の場合
最初の操作 $(T_1)$ で、 $1$ は左端に移動する。この後の2番目以降の並び方は、(a)のときと1対1に対応する。よって、この場合は $c_{n-1}$ 通り。
上の2つのケース以外は、(1)より、 $A_1,A_2$ のどちらかが $2$ で、どちらかが $3$ 以上のケースしかない。
(c) $A_1=2$, $A_2\geqq 3$ の場合
最初の操作 $(T_1)$ で入れ替えは発生しない。 $A_2$ から $A_n$ の数のうち、 $3$ 以上の数を $1$ ずつ減らすと、 $(n-1)$ 枚を使ったときの「うまくいく並べ方」のうち、左端が $1$ でない並べ方が得られる。
逆に、 $(n-1)$ 枚を使ったときの「うまくいく並べ方」のうち、左端が $1$ でない並べ方に対し、 $2$ 以上の数に $1$ を足し、左端に $2$ を並べれば、この場合の「うまくいく並べ方」が得られる。
なお、$(n-1)$ 枚を使ったときの「うまくいく並べ方」は $c_{n-1}$ 通りあり、このうち、左端が $1$ の並び方は、(a)より $c_{n-2}$ 通りある。よって、この場合の「うまくいく並べ方」の総数は $(c_{n-1}-c_{n-2})$ 通り。
(d) $A_1\geqq 3$, $A_2=2$ の場合
最初の操作 $(T_1)$ で、 $2$ は左端に移動する。この後の2番目以降の並び方は、(c)のときと1対1に対応する。よって、この場合は $(c_{n-1}-c_{n-2})$ 通り。
以上から、
\begin{eqnarray}
c_n &=& c_{n-1}+c_{n-1}+(c_{n-1}-c_{n-2})+(c_{n-1}-c_{n-2}) \\[5pt]
&=& 4c_{n-1}-2c_{n-2}
\end{eqnarray}と表すことができる。（答）
