南北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地点までの最短経路の数は、$\frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10$

A地点からP地点までの最短経路の数は、$\frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$

O地点からA地点を通りP地点までの最短経路の数は、$10 \times 10 = 100$

(2) O地点からB地点までの最短経路の数と、B地点からP地点までの最短経路の数を求め、それらを掛け合わせる。

O地点からB地点までの最短経路の数は、$\frac{5!}{4!1!} = 5$

B地点からP地点までの最短経路の数は、$\frac{5!}{1!4!} = 5$

O地点からB地点を通りP地点までの最短経路の数は、$5 \times 5 = 25$

(3) O地点からA地点に行き、その後B地点に行き、P地点へ行く場合と、O地点からB地点に行き、その後A地点に行き、P地点へ行く場合がある。

AとBの間はC地点を通れないので、道を考えるときには注意する必要がある。

OからAへの経路は10通り。AからBへの経路はOからAへ行き、Cを通らずにBへ行く必要がある。AからCを通ってBへは行けないので、AからBへの経路は、Aから南に2つ、東に2つ進む経路の数から、Cを通る経路を除けば良い。しかし、AからBへ行く際にCを通ることはできないので、単純にAからBへの最短経路の数を計算すれば良い。AからBへの最短経路の数は、$\frac{4!}{2!2!} = 6$ 通り。BからPへの経路は5通りなので、O -> A -> B -> P の経路の数は $10 \times 6 \times 5 = 300$

OからBへの経路は5通り。BからAへの経路は、$\frac{4!}{2!2!} = 6$ 通り。AからPへの経路は10通りなので、O -> B -> A -> P の経路の数は $5 \times 6 \times 10 = 300$

合計の経路数は $300 + 300 = 600$通り

3. 最終的な答え

(1) 100通り

(2) 25通り

(3) 600通り