を 以上の整数とする。 から までの数字が書かれた札が各 枚ずつ合計 枚あり，横一列におかれている。 以上 以下の整数 に対して，次の操作 を考える。
左から 番目の札の数字が，左から 番目の札の数字よりも大きければ，これら 枚の札の位置を入れかえる。そうでなければ，札の位置をかえない。
最初の状態において札の数字は左から , , , であったとする。この状態から 回の操作 , , , を順に行った後，続けて 回の操作 , , , を順に行ったところ，札の数字は左から , , , と小さい順に並んだ。以下の問いに答えよ。
(1) と のうち少なくとも一方は 以下であることを示せ。
(2) 最初の状態としてありうる札の数字の並び方 , , , の総数を とする。 が 以上の整数であるとき， を と を用いて表せ。
前向きの走査は、隣どうしを左から順に比べて、大きいほうを右へ送っていく動きです。1 回で最大の札が右端へ着きます。
後ろ向きの走査は、その逆です。小さいほうを左へ送っていくので、1 回で最小の札が左端へ着きます。
この 2 回だけで小さい順に並ぶ、というのが条件です。図で 1 手ずつ追ってみてください。
言いかえると、札は前向きの走査で左へ 1 つしか動けず、後ろ向きの走査で右へ 1 つしか動けません。遠くへ運ばれるのは、送られていく側になったときだけです。
前向きの走査で 1 番目の札に触るのは、最初の だけです。そこで小さいほうが 1 番目に残り、そのあと 1 番目は動きません。
つまり前向きの走査を終えた時点で、1 番目の札は と の小さいほうです。これを と書きます。
後ろ向きの走査で 1 番目に触るのも、最後の だけです。その直前までに、2 番目以降だけの走査が済んでいます。
2 番目以降だけの走査は、その中の最小値を 2 番目へ運びます。だから最後の の直前は、1 番目が 、2 番目が「残り全部の最小値」 という形です。
最後の は、 と を比べて小さいほうを 1 番目に置きます。終わったあとの先頭 2 枚は、 と を小さい順に並べたものです。
並び終わりは , , ですから、2 番目は です。つまり と のうち大きいほうが で、両方とも 以下ということになります。
とくに です。 は と の小さいほうでしたから、 と のうち少なくとも一方は 以下です。
これで (1) が示せました。ここで出てきた「先頭の 2 枚から小さいほうが抜ける」という形が、そのまま (2) の数え方になります。
最初の のあと、残りの前向きの走査は「, , , 」という 枚に対する同じ走査です。後ろ向きも、 枚の走査を済ませてから最後に を行う形です。
のとき。最後の では入れかわらないので、 枚がそのまま小さい順に並ぶことが条件です。つまり「, , , 」が 枚の条件を満たす並びであればよく、 と の左右で 2 通りずつ。 通りです。
のとき。 は 3 番目以降のどこかにいるので となり、最後の で入れかわって先頭が , とそろいます。3 番目以降がそろう条件は、やはり「, , , 」が 枚の条件を満たすことです。
ただしこの場合は 、つまり は 枚の中の最小ではありません。先頭が最小になる並びは、同じ議論から 通りありますから、使えるのは 通り。左右で 2 倍して 通りです。
2 つの場合は重なりません。 が か かで分かれており、(1) よりそれ以外は起こらないからです。
たして となります。これが答えです。
出発点は 、 です。 枚と 枚では、どの並びも 2 回の走査で小さい順に並びます。
漸化式を回すと 、、 と続きます。 に比べるとずっとゆっくりで、条件がかなりきついことが分かります。