4199 (= 13×17×19) 個の箱があります。これらの箱は透明の板で作られていて、中が見えるようになっています。さて、これらの箱の中に一箱に一枚ずつ数字の書いてあるカードを入れていきます。カードに書いてある数字は好き勝手な（正の）整数 (*) です。その後、カードが入った箱を 13×17×19 のブロックに積み上げます。ここで、便宜上、長さ 13、高さ 17の面を正面と呼びます。（もちろん、奥行きが 19 になるわけです。）この時点ではカードの並びはバラバラです。そこで、左下正面から右上奥に向けて中にはいっているカードの数字が大きくなるようにしていこうと思います。つまり、ブロックのどの部分を見ても、左から右に向けて数字が大きくなるように、また、同じように下から上に向けて、手前から奥に向けて数字が大きくなるようにします。但し、次のような手順で箱を並べ換えるものとします：
さて、色々な数字の入れ方や最初の箱の並べ方によって、このような手順で最高何ステップかかることがあるでしょうか？
| 注意 1： | 最高ステップ数のときの数字の入れ方や最初の箱の配置を答える必要はありません。 |
| 注意 2： | このような手順をいくら繰り返しても、望む配置にならないような数字の入れ方、最初の箱の配置がある場合は、答には 0 を入れて下さい。 |
| 注意 3： | 2 回目の第 1 ステップを第 4 ステップ、2 回目の第 2 ステップを第 5 ステップと数えていきます。 |
| (*) | 1 以上の整数をランダムに書いていきます。もちろん、違うカードに同じ数字が書かれることもあるかも知れません。 |
| (**) | 「望みの配置」とは、左下正面から右上奥に向けて数字が大きくなる箱の配置のことです。 |
※ 数字の並べ方で、同じ数字の並びは条件を満たしています。つまり、数字は小さくはならないということです。 (12/19付記)
出題： tomh さん
解答： 3 ステップ
解説：
どのような数字の入れ方をしても、どのような箱の積み上げ方を最初に しても、最高で３方向の並び換えを行うことで望みの配置になります。 まず、次のようなことを考えてみましょう。 ある学校には３００人の生徒がいます。この３００人を３０人×１０列に適当 に並べます。ところが適当に並んだために、背の高さがバラバラで、正面から 見て顔の見えない生徒がいます。そこで、背の順に並べ換えるために、次のよ うな手続きを行います。 ・まず、縦の１０列（１列３０人）をそれぞれ前に背の低い人がいるように並べ換 えます。（第１ステップ） ・次に生徒たちの左側に行き、横の３０列（１列１０人）をそれぞれ（正面か ら見て）左側に背の低い人が来るように並べ換えます。（第２ステップ） このようにして、再び正面に戻ってみると…せっかく並べた縦の列が乱れてい るかと思ったら、やっぱり背の順にきれいに並んでいて、正面左前から生徒を 見ると、見事、右奥に向かって、背の順に並んでいることがわかります。 これは、次のように説明できます。 上の２ステップが終った後、背の高い人が低い人の前にいる縦の列があったと します。その列の中で順番が逆転している誰か２人を選び出して、背の低い人 （つまり、後ろにいる人）をＡ、背の高い人（つまり、前にいる人）をＢとし ます。 このとき、（第２ステップが終った直後ですから）Ａの左側にはＡより背の低 い人がいるはずです。同じようにＢの右側にはＢより背の高い人がいるはずで す。（図１参照） さて、ここから第２ステップの分だけ、時間を逆戻りしてみましょう。 すると、（図１を見ればわかるように）Ａとその左側の人たち（第１グループ とでも呼んでおきましょう。）とＢとその右側の人たち（同じく第２グループ とします。）を合わせると１１人います。縦列は１０列しかありませんから、 少なくとも第１グループの人と第２グループの人が同時にいる縦列が一つはあ るはずです。その列の第１グループに入る人をａ、第２グループに入る人をｂ とします。（図２参照） 第１グループの人たちは、全員が第２グループの人たちよりも背の低い人たち のはずでしたから、ａもｂより背が低いはずです。ところが、図２の状態は、 上記の第１ステップが終った直後ですから、縦列は整然と前から順番に背の低 い人から高い人へと並んでいるはずで矛盾しています。これは、２ステップが 終った後に背の高い人が低い人の前にいる縦の列があったと最初に仮定したこ とが間違っていたためです。 よって、２ステップが終った後、生徒は左から右へ、かつ、前から後ろへ背の 低い人から背の高い人の順に並ぶことがわかります。 このことが縦列の数や横列の数に関係なく、また、各人の背の高さがいくらで あっても成り立つことに注意しましょう。 【図１】 １０列 ┌───────────────┐ │ ‖ │ │ ‖ │ │□□□□□Ａ │ │ ‖ │ │ ‖ │ │ ‖ │ │ ‖ │ ３０列 │ ‖ │ │ ‖ │ │ ‖ │ │ Ｂ■■■■■■■■■│ │ ‖ │ │ ‖ │ │ ‖ │ │ ‖ │ └───────────────┘ （正面） 【図２】 １０列 ┌───────────────┐ │ ‖ │ │ ‖ │ │ ａ │ │ ‖ │ │ ‖ │ │ ‖ │ │ ‖ │ ３０列 │ ‖ │ │ ‖ │ │ ‖ │ │ ｂ │ │ ‖ │ │ ‖ │ │ ‖ │ │ ‖ │ └───────────────┘ （正面） さて、今、考えた状況は、平面上の場合です。今回の問題は、これの立体バー ジョンです。 問題にある第２ステップまでは、平面バージョンの第２ステップと同じですか ら、第２ステップ終了後には１７枚の階層それぞれで左から右、かつ、手前か ら奥へ数字小さいものから大きいものへと並ぶはずです。 もし第３ステップで左から右に並んでいる３２３列のうちで、数字の大きいカー ドが入った箱が小さい数字が入った箱の左に来るような列が一つでもできたと します。このときは、その列を含む１３×１７の箱の壁を考えて、先ほどの平 面で行った手続きをこの壁で繰り返すとやはり矛盾しますので、第３ステッ プの後でこれら３２３列すべてが、左から右に数字が小さいものから大きいも のへと順番に並んだ状態を保つことがわかります。同じように手前から奥へと 並ぶ２２１列でこの考え方を繰り返せば、やはり第３ステップ後、手前から奥 へと小さい数字から大きい数字の順番に並んだ状態が保たれることがわかりま す。 よって、第３ステップの後で３方向とも望みの並び方になることがわかったの で、多くても３ステップあれば十分なことがわかりました。 また、実際に３ステップ必要な数字の入れ方、箱の配置として、 左上正面に「３」、右下奥に「５」、残りの箱に「６」 というのがありますから、答は３ステップです。
お問い合わせは aki(at)angel.ne.jp までどうぞ。