南北に7本、東西に6本の道があるグリッド状の道路網において、以下の3つの場合の最短経路の数を求める問題です。ただし、C地点は通れないものとし、1区間の距離は南北、東西で等しいとします。 (1) O地点からA地点を経由してP地点へ行く最短経路の数 (2) O地点からB地点を経由してP地点へ行く最短経路の数 (3) O地点からA地点とB地点の両方を経由してP地点へ行く最短経路の数

1. 問題の内容

南北に7本、東西に6本の道があるグリッド状の道路網において、以下の3つの場合の最短経路の数を求める問題です。ただし、C地点は通れないものとし、1区間の距離は南北、東西で等しいとします。

(1) O地点からA地点を経由してP地点へ行く最短経路の数

(2) O地点からB地点を経由してP地点へ行く最短経路の数

(3) O地点からA地点とB地点の両方を経由してP地点へ行く最短経路の数

2. 解き方の手順

最短経路の数は、右方向への移動回数と下方向への移動回数が決まれば一意に決まります。組み合わせの考え方を利用します。OからPまでの最短経路の場合、右に5回、下に6回移動するので、合計11回の移動のうち、右方向への移動をどこに配置するかを考えればよいです。これは $_{11}C_5$ あるいは $_{11}C_6$ で計算できます。

ただし、経由地がある場合は、それぞれの区間の移動回数を計算し、その積を求めます。また、C地点を通れないという条件を考慮する必要があります。

(1) O地点からA地点へ行く最短経路の数は、右に3回、下に1回移動するので、$_{4}C_3 = 4$通りです。A地点からP地点へ行く最短経路の数は、右に2回、下に5回移動するので、$_{7}C_2 = \frac{7 \times 6}{2 \times 1} = 21$通りです。したがって、O地点からA地点を経由してP地点へ行く最短経路の数は、$4 \times 21 = 84$通りです。

(2) O地点からB地点へ行く最短経路の数は、右に1回、下に4回移動するので、$_{5}C_1 = 5$通りです。B地点からP地点へ行く最短経路の数は、右に4回、下に2回移動するので、$_{6}C_4 = _{6}C_2 = \frac{6 \times 5}{2 \times 1} = 15$通りです。したがって、O地点からB地点を経由してP地点へ行く最短経路の数は、$5 \times 15 = 75$通りです。

(3) O地点からA地点へ行く最短経路の数は4通り、A地点からB地点へ行く最短経路は存在しません。したがってA地点とB地点の両方を通ることはありません。また、C地点を通れないという条件があるので、Cを通る経路は存在しません。したがって、0通りです。

別の考え方として、A,B,Pの位置関係より、AからBへの最短経路は存在しないため、AとB両方を通ってPまで行くことはできません。

3. 最終的な答え

(1) 84通り

(2) 75通り

(3) 0通り