格子点を水平・垂直の直交二方向の経路で結び、様々な条件のもとで最短経路を探っていく、定番の格子状経路問題。
今回は、
「停止したままとなる場合がある」
という設定のもとで取り組んでみましょう。
【問題】
まず、座標平面上で
「点A(0,0),点B(4,0),点C(4,3),点D(0,3)」
とし、
「長方形ABCDの内部（辺上も含む）の全ての格子点を水平・垂直の直交二方向の経路で結んだ場合」
を考えます。
「点Aからスタート」
し、
「上か右の格子点に順次進む」
ことを繰り返しながら、
「点Cに至る最短経路」
を探っていくのですが、次にどの格子点に進むかは
「コインを投げる」
ことで決めていきます。
「コインの“表が出れば上”、“裏が出れば右”」
の格子点へと進むこととし、
「その方向に格子点がない場合は停止したまま」
とします。
点Aからスタートし、例えば
「3回続けてコインの表が出れば点D」
に至りますが、
「次も表が出たら点Dで停止したまま」
となります。
このとき、
「コインを10回投げて初めて点Cにたどり着く」
ようなコインの表裏の出方は何通りでしょうか？
【解説】
まず、停止することがなければ、
「コインを7回投げる」
ことで、点Cにたどり着くことができますね。
つまり、題意を満たすには、
「3回停止することがあった」
ということになります。
ここで大切なのは、
「10回のうち3回停止するのだから…」
とトータルで考えていってしまうと、カウントミスが起きやすくなります。
そこで、停止する可能性があるのは、
「辺BC上か辺CD上の格子点にあるとき」
なので、
「点Cに至る一つ手前」
の状況に着目して攻めていくべきですね。
(ⅰ) (4,2)から点Cに至る場合
「ここに至る9回のうち2回のみ表が出る」
という条件にしておけば、
「右方向へ行けずに停止する全ての場合」
をカウントすることができ、
「9C2=36通り」
あることがわかります。
(ⅱ) (3,3)から点Cに至る場合
「ここに至る9回のうち3回のみ裏が出る」
という条件にしておけば、
「上方向へ行けずに停止する全ての場合」
をカウントすることができ、
「9C3=84通り」
あることがわかります。
∴36+84=120通り
（2024慶應義塾志木・改題）
