人力シェーカーソート問題 – 2025年東大 数学 第5問
2025年東大 数学 第5問 小問2の解法
カードには左から順に番号が振られているので、漸化式を考えるにあたっては右側にカードを増やしていくのが自然な発想です。カードを右側に増やしていくと左側のカードの並び方にうまくアドオンできそうな気がします。
そこで右側の2枚にフィーチャーします。すると小問1と同様にして、オペレーションの結果カードが昇順に並ぶならば、An-1 と An の少なくとも一方は n-1 以上であることがわかります。大きい数がある程度右に集まっている必要があるということなので、これを場合分けして漸化式を導出します。
An-1 と An の双方が n-1 以上の場合
この場合、右の2枚が最も大きい2枚なので、右の2枚とそれ以外はオペレーションによって入れ替わることはありません。
したがって左側 n-2 枚のカードの並び方は cn-2 、右2枚の並び方は2通りなので、並び方の総数は
2cn-2
です。
An が n-1 以上で An-1 が n-1 未満の場合
一番右が n か n-1 のいずれかで、その隣の An-1 が n-1 未満の場合です。
\begin{aligned}
\overbrace {
\underset{ \substack{ \uparrow \\n-1 \\\text{未満} } }
{\fbox { $ A_1 $} }
\,
\underset{ \substack{ \uparrow \\n-1 \\\text{未満} } }
{\fbox { $ A_2 $} }
\cdots
\underset{ \substack{ \uparrow \\n-1 \\\text{or} \,n } }{
\colorbox{black}{ $ \color{white}{A_i }$} }
\cdots
\underset{ \substack{ \uparrow \\n-1 \\\text{未満} } }
{\fbox { $ A_{n-2} $} }
}^{n -2\text{枚}}
\overset{ \substack{n-1 \\ \text{未満} \\ \downarrow } }{
\, \fbox{ $A_{n-1}$} }
\overset{ \substack{ n-1 \\\text{or} \,n \\ \downarrow } }{
\,\colorbox{black}{ $ \color{white}{A_n }$} }
\end{aligned}「上り方向」のオペレーション（1回目の (T1),(T2),…,(Tn-1)）が終了した時点で、カードの並びは以下のようになります。
\begin{aligned}
\overbrace {
\fbox{ $\color{white}A_1$} \,\fbox{ $\color{white}A_2$} \cdots \fbox{ $\color{white}A_{n}$}
}^{n -2\text{枚(n-1未満)}}
\,\colorbox{black}{ $ |\scriptsize{\color{white}{n -1}}$}
\,\colorbox{black}{ $ |\color{white}{ n }$}
\end{aligned}その後2回めの (Tn-1) を実施した時点で右から2番めのカードは n-1 です。1回目の (Tn-2) を実施した結果と異なる場合がありますが、その場合でも左側の n-1 枚の中では最大です。よってそれ以降の (Ti) の結果に影響しません。
すなわち、 n 枚のカードに対するオペレーションの結果カードが昇順に並んでいることと、そのうちの左側 n-1 枚のカードに対して (T1),(T2),…,(Tn-2)→(Tn-2),(Tn-3),…,(T1) を実施した結果、カードが（一番右側のカードの入れ替わりを除いて）昇順に並ぶことは同値です。したがって左側 n-1 枚の初期配置数は cn-1 です。
と言いたいところですが、よく考えるとその並び方の中には、初期配置の右から2番目すなわち An-1 が n または n-1 である場合も含まれます。それらのケースはすでにカウント済みなので差し引く必要があります。
An-1 が n または n-1 である場合の数は cn-2 なので、それを差し引いた
cn-1 – cn-2
が左側 n-1 枚の初期配置数です。
一番右側のカード An は値が n と n-1 の2パターンあるので、求める場合の数は
2(cn-1 – cn-2)
です。
An が n-1 未満で An-1 が n-1 以上の場合
右から2番めの An-1 が n か n-1 のいずれかで、一番右が n-1 未満の場合です。
\begin{aligned}
\overbrace {
\underset{ \substack{ \uparrow \\n-1 \\\text{未満} } }
{\fbox { $ A_1 $} }
\,
\underset{ \substack{ \uparrow \\n-1 \\\text{未満} } }
{\fbox { $ A_2 $} }
\cdots
\underset{ \substack{ \uparrow \\n-1 \\\text{or} \,n } }{
\colorbox{black}{ $ \color{white}{A_i }$} }
\cdots
\underset{ \substack{ \uparrow \\n-1 \\\text{未満} } }
{\fbox { $ A_{n-2} $} }
}^{n -2\text{枚}}
\overset{ \substack{ n-1 \\\text{or} \,n \\ \downarrow } }{
\,\colorbox{black}{ $ \color{white}{A_{n-1} }$} }
\overset{ \substack{n-1 \\ \text{未満} \\ \downarrow } }{
\, \fbox{ $A_{n}$} }
\end{aligned}「上り方向」のオペレーション（1回目の (T1),(T2),…,(Tn-1)）が終了した時点で、カードの並びは以下のようになります。
\begin{aligned}
\overbrace {
\underbrace{
\fbox{ $\color{white}A_1$} \,\fbox{ $\color{white}A_2$} \cdots \fbox{ $\color{white}A_{n}$}
}_{n -1\text{未満}}
\,\colorbox{black}{ |$ \scriptsize\color{white}{n -1}$}
}^{n -2\text{枚}}
\overset{ \substack{n-1 \\ \text{未満} \\ \downarrow } }{
\, \fbox{ $A_{n}$} }
\,\colorbox{black}{ |$ \color{white}{ n }$}
\end{aligned}左側 n-1 枚のうちの一番右が An で、それはそれらのカードの中で最大ではありません。カードの枚数が n-1 のとき、上りのオペレーションが終了した時点でそういう並び方はありえないので、オペレーションの結果カードが昇順に並んでいるときの、左側 n-1 枚の初期配置数が cn-1 かどうかはわかりません。
では何パターンあるのかは、An の値を細かく場合分けする必要が出てきて一筋縄では行きません。このアプローチは袋小路です。