人力シェーカーソート問題 – 2025年東大 数学 第5問
A1 と A2 の双方が 2 以下の場合
右側の2枚にフィーチャーするのはうまく行かなかったので、今度は左側から攻めます。
左側にフィーチャーするとオペレーションの途中でカードが入れ替わる撹乱要因が発生しないので、今度はうまく行きそうな気がします。
そこでまず、左側の2枚が1または2の場合です。この場合、左の2枚とそれ以外はオペレーションによって入れ替わることはありません。
右側のカードは 3 から n までの n-2 枚ですが、オペレーションは大小を比較するだけでカードの値それ自体は問題にしません。よってオペレーションの結果 3 から n までの n-2 枚が昇順に並ぶ初期配置数と、 1 から n-2 までの n-2 枚が昇順に並ぶ初期配置数は同じで cn-2 です。
左2枚の初期配置数は2通りなので、並び方の総数は
2cn-2
です。
A1 が 2 以下で A2 が 3 以上の場合
\begin{aligned}
\overset{ \substack{ 1 \, \text{or} \,2 \\ \downarrow } }{
\,\colorbox{black}{ $ \color{white}{A_1 }$} }
\overset{ \substack{ 3\text{以上} \\ \downarrow } }{
\, \fbox{ $A_{2}$} }
\,
\overbrace {
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_3 $} }
\,
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_4 $} }
\cdots
\underset{ \substack{ \uparrow \\1 \, \text{or} \,2 } }{
\colorbox{black}{ $ \color{white}{A_i }$} }
\cdots
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_{n} $} }
}^{n -2\text{枚}}
\end{aligned}明らかに、オペレーションの結果 n 枚のカードが昇順に並ぶことと、右側 n-1 枚のカードが(T2),(T3),…,(Tn-1)→(Tn-1),(Tn-2),…,(T2) の結果昇順に並ぶことは同値です。
よって右側 n-1 枚の初期配置数は cn-1 だと言いたいところですが、そこには A2 が1または2である場合の数も含まれます。その数は cn-2 なので差し引いて
cn-1 – cn-2
が右側 n-1 枚の初期配置数です。
一番左側の A1 の値は1か2の2パターンあるので、A1 が 2 以下で A2 が3以上の場合の初期配置数は
2(cn-1 – cn-2)
です。
A1 が 3 以上で A2 が 2 以下の場合
\begin{aligned}
\overset{ \substack{ 3\text{以上} \\ \downarrow } }{
\, \fbox{ $A_{1}$} }
\overset{ \substack{ 1 \, \text{or} \,2 \\ \downarrow } }{
\,\colorbox{black}{ $ \color{white}{A_2 }$} }
\,
\overbrace {
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_3 $} }
\,
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_4 $} }
\cdots
\underset{ \substack{ \uparrow \\1 \, \text{or} \,2 } }{
\colorbox{black}{ $ \color{white}{A_i }$} }
\cdots
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_{n} $} }
}^{n -2\text{枚}}
\end{aligned}最初の (T1) 実施後の並びは
\begin{aligned}
\overset{ \substack{ 1 \, \text{or} \,2 \\ \downarrow } }{
\,\colorbox{black}{ $ \color{white}{A_2 }$} }
\overset{ \substack{ 3\text{以上} \\ \downarrow } }{
\, \fbox{ $A_{1}$} }
\,
\overbrace {
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_3 $} }
\,
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_4 $} }
\cdots
\underset{ \substack{ \uparrow \\1 \, \text{or} \,2 } }{
\colorbox{black}{ $ \color{white}{A_i }$} }
\cdots
\underset{ \substack{ \uparrow \\3\text{以上} } }
{\fbox { $ A_{n} $} }
}^{n -2\text{枚}}
\end{aligned}です。これが昇順に並ぶための初期配置数は先に見たように、2(cn-1 – cn-2) です。したがってA1 が 3 以上で A2 が 2 以下の場合の初期配置数も
2(cn-1 – cn-2)
です。
ゆえに
\begin{aligned}
c_n = & 2c_{n-2} + 2(c_{n-1} - c_{n-2})+ 2(c_{n-1} - c_{n-2}) \\
= & 4c_{n-1} - 2 c_{n-2}
\end{aligned}です。