人力シェーカーソート問題 – 2025年東大 数学 第5問
2025年東大 数学 第5問 はソートアルゴリズムの一種、シェーカーソートを使ってカードを人力で昇順ソートする問題です。問題文は以下のとおりで、東大2次試験からの引用です。
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 を用いて表せ。
オペレーションの内容は、2枚のカードを比較して左側の数字が大きければ左右を入れ替えるというのを、まず左から右に行い、次いで右から左に行います。このソート方法をシェーカーソートと呼びます。
本来のシェーカーソートはこのオペレーションをカードが完全に昇順に並ぶまで行うのですが、本問では上り下りの1往復しか実施しません。1往復だけでも数字の大きいカードほど列の右側に、数字の小さいカードほど左側に集まる傾向があり、特に n は必ず右端に、1 は必ず左端に来ますが、すべてのカードが常に昇順に並ぶわけではありません。
そこで1往復のオペレーションだけでカードが完全に昇順に並ぶために、カードの初期配置が満たすべき必要条件やその場合の数を求めよ、というのが本題の主旨です。
割と何とかなりそうな気もしますが、取り敢えず見ていきましょう。なお、本稿の内容は東大が発表したものではありません。
2025年東大 数学 第5問 小問1の解法
これはなんとなく明らかです。オペレーションのロジックにより、一旦一番左に寄ってしまったカードは絶対に左から3番目以降に移動しないからです。
そこでA1 と A2 の双方とも3以上であると仮定します。するとオペレーションの初手(T1)で一番左にA1 と A2 の小さいほうが来ます。これを A と置きます。仮定により、 A ≧ 3 です。
一連のオペレーションのうち、最後から2番めの(T2)を実施した時点で A の右隣、左から2番めのカードは 1 です。
したがって最後のオペレーション(T1)を実施すると、カードの並びは左から1,A ,… となります。 A ≧ 3 であったのでカードは昇順に並んでいません。
以上の対偶を取ることにより、オペレーションの結果カードが昇順に並ぶならば、A1 と A2 の少なくとも一方は 2 以下であることが証明できました。