右の図のような道路網があり、南北に7本、東西に6本の道がある。C地点は通れない。1区間の距離は南北、東西で等しい。以下の問いに答える。 (1) O地点を出発し、A地点を通り、P地点へ最短距離で行く道順は何通りあるか。 (2) O地点を出発し、B地点を通り、P地点へ最短距離で行く道順は何通りあるか。 (3) O地点を出発し、A地点とB地点の両方を通って、P地点へ最短距離で行く道順は何通りあるか。同じ道を何度通ってもよい。

1. 問題の内容

右の図のような道路網があり、南北に7本、東西に6本の道がある。C地点は通れない。1区間の距離は南北、東西で等しい。以下の問いに答える。

(1) O地点を出発し、A地点を通り、P地点へ最短距離で行く道順は何通りあるか。

(2) O地点を出発し、B地点を通り、P地点へ最短距離で行く道順は何通りあるか。

(3) O地点を出発し、A地点とB地点の両方を通って、P地点へ最短距離で行く道順は何通りあるか。同じ道を何度通ってもよい。

2. 解き方の手順

(1) OからAへ行く最短経路の数と、AからPへ行く最短経路の数をそれぞれ求め、それらを掛け合わせる。

OからAへ行くには、東に2区画、北に2区画進む必要があるので、最短経路の数は $_{4}C_{2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通り。

AからPへ行くには、東に3区画、北に4区画進む必要があるので、最短経路の数は $_{7}C_{3} = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通り。

したがって、OからAを経由してPへ行く最短経路の数は $6 \times 35 = 210$ 通り。

(2) OからBへ行くには、東に1区画、南に2区画進む必要があるので、そのような経路は存在しない。したがって、C地点が通れないという条件に関わらず、OからBを通ってPに行く経路は存在しない。ゆえに、経路数は0通りである。しかし、問題文に「なお、同じ道を何度通ってもよいとする。」と書いてあるので、OからBへ、BからOへ、OからPへと進むことはできる。OからBに行くには、東に1区画、南に2区画進む必要がある。B地点を通ると最短距離ではないので、B地点へ行く経路は存在しない。そのため、最短距離で行く道順は0通りである。

(3) OからAへ行く最短経路数は6通り、OからBへ行く最短経路は存在しない。AからPへ行く最短経路数は35通り。BからPへ行く最短経路は存在しない。O地点を出発し、A地点とB地点の両方を通って、P地点へ最短距離で行く経路は存在しない。したがって、経路数は0通り。ただし、同じ道を何度通ってもよい、という条件が加わる。まずOからAへ行き、次にAからBへ行く。その後、BからPへ行く経路数を考える。しかしA地点とB地点を通る最短距離の経路は存在しないので経路数は0通り。

3. 最終的な答え

(1) 210通り

(2) 0通り

(3) 0通り