格子状“立体”経路問題

少し前になりますが、『CUBE』という映画が2～3本の続編も含めて上映されていました。

最初は何かB級映画的な雰囲気を漂わせているものの、推理的要素にどんどん引き込まれていくような展開となっていくのですが、その舞台が“CUBE状に構築された空間”となっています。

（※日本でも様々に制作されている“脱出ゲーム系”映画のはしりとも言えると思いますが、描写的に過激な内容も含まれているので、学生の皆さんは注意してくださいね。）

今回は、その舞台をどうしても思い出してしまう
「立体的に構築された格子状経路」
に関する問題です。

「最短経路問題」としては頻出パターンなので、取り組み方を“叩き込まれた”受験生も多いかもしれませんが、原理を理解できていない場合はしっかり再確認しておきましょう。

取り組み方としては、
「平面における格子状経路問題」
と基本的に同じで、ただそれを
「三次元に拡張させて考える」
だけです。

なお、二次元の場合は、
「x-y座標“平面”における格子点」
をイメージして考えていきましたが、今回は立体なので、
「x-y-z座標“空間”における格子点」
をつなぐ経路で考えていくことになります。

※条件設定を誤解のないように説明するために問題文は長くなってしまいます。

【問題】
一辺1の立方体12個を
「縦2横3高さ2の直方体ABCD-EFGH」
となるように積み重ねる。

「立方体の各辺を経路」
として、直方体の対角線の端点である
「点Aから点Gに至る最短経路」
を考える。

但し、立方体の辺どうしが接する部分は「一つの経路」と考え、立方体の各頂点で「次にどの方向の格子点に進むか」を選択していく。

最短経路を考えるので、進む方向としては、
「A→Bと平行な方向（x軸方向）」
「A→Dと平行な方向（y軸方向）」
「A→Eと平行な方向（z軸方向）」
の3方向に分類される。

このとき、
(1)「点Aから点Gに至る最短経路」
(2) (1)のうち「直方体の表面上のみを通る経路」
は何通りあるか？

【解説】
「縦、横、高さのいずれかの長さが1」
であるような直方体であれば、
「平面経路における特定点を通る場合」
の考え方を応用すれば、対称性から
「表面上の最短経路数」
を求めることも簡単です。

しかし、今回のような
「縦、横、高さのいずれかも長さが2以上」
の直方体の場合は、上記のような考え方をしていると“日が暮れて”しまいますね。

そこで、下記のような考え方ができるようにしておきましょう。

(1)
表面上に限らず、内部を通る場合も含めて、
「点Aから点Gに至る最短経路」
を考える場合は、
「7回進む方向を選択」
することになりますね。

そのうちの
「2回をx方向,3回をy方向,2回をz方向」
に選択していけば点Gに至るので、
∴ 7C2×5C2=210通り

(2)
余事象で考えていった方がいいでしょう。

つまり、
「直方体の内部の格子点を通る場合」
をカウントしていきましょう。

そのような格子点は2個あるので、
「点Aに近い方を点P、他方を点Q」
としましょう。

(ⅰ) 点Pを通る場合
平面経路の場合と同様に考えて、(3C1×2C1)×(4C1×3C1)=72通り
（※「点Qも通る場合」も含まれていますね）

(ⅱ) 点Qのみを通る場合
(4C1×3C1-3C1×2C1)×(3C1×2C1)=36通り

よって、余事象である
「内部の格子点を通る場合=108通り」
となるので、
∴210-108=102通り

（2024渋幕・改題）