南北に7本、東西に6本の道がある街において、O地点から出発し、指定された地点（A, B）を通り、P地点まで最短距離で行く経路の数を求める問題です。ただし、C地点は通れません。 (1) O地点からA地点を通り、P地点へ行く経路の数 (2) O地点からB地点を通り、P地点へ行く経路の数 (3) O地点からA地点とB地点の両方を通り、P地点へ行く経路の数

## 回答

1. 問題の内容

南北に7本、東西に6本の道がある街において、O地点から出発し、指定された地点（A, B）を通り、P地点まで最短距離で行く経路の数を求める問題です。ただし、C地点は通れません。

(1) O地点からA地点を通り、P地点へ行く経路の数

(2) O地点からB地点を通り、P地点へ行く経路の数

(3) O地点からA地点とB地点の両方を通り、P地点へ行く経路の数

2. 解き方の手順

最短経路の数を求める問題なので、各地点までの経路数を書き込んでいく方法で解きます。O地点から各地点への最短経路の数は、その地点の左と下の数字を足し合わせたものになります。ただし、C地点は通れないので、C地点とその先の地点への経路数は0になります。

(1) O地点からA地点を通り、P地点へ行く経路の数

* OからAまでの最短経路の数を求める。A地点はO地点から東に2つ、北に2つ移動した場所にあるので、OからAまでの経路数は $\frac{4!}{2!2!} = 6$通り。

* AからPまでの最短経路の数を求める。A地点からP地点までは、東に3つ、北に1つ移動した場所にあるので、AからPまでの経路数は $\frac{4!}{3!1!} = 4$通り。

* OからAを通ってPへ行く経路数は、$6 \times 4 = 24$通り。

(2) O地点からB地点を通り、P地点へ行く経路の数

* OからBまでの最短経路の数を求める。B地点はO地点から東に1つ、南に3つ移動した場所にあるので、OからBまでの経路数は $\frac{4!}{1!3!} = 4$通り。

* BからPまでの最短経路の数を求める。B地点からP地点までは、C地点を通れないことに注意して、各地点への経路数を書き込んでいく。

* BからCの右下の点までの経路数は 1通り

* Cの右下の点からPまでの経路数は $\frac{4!}{2!2!} = 6$通り

* BからPまでの経路数は$3 + 6 = 9$通り

* OからBを通ってPへ行く経路数は、$4 \times 9 = 36$通り。

(3) O地点からA地点とB地点の両方を通り、P地点へ行く経路の数

* OからA, Bを通ってPへ行く経路は、O→A→B→P, O→B→A→P の2通り考えられる。

ただし、同じ道を何度通っても良いので、それぞれの経路数を求める。

* O→A→B→Pの経路数

* OからAまでの経路数は6通り（(1)で計算済み）

* AからBまでの最短経路の数を求める。AからBへは南に1つ、西に1つ進む必要があり最短距離では到達できないため、Aからいったん北に戻るか東に戻って回り道をする必要がある。最短経路数は0通り

* よってO→A→B→Pの経路数は0通り

* O→B→A→Pの経路数

* OからBまでの経路数は4通り（(2)で計算済み）

* BからAまでの最短経路の数を求める。同様に、B地点からA地点までは、北に1つ、西に1つ進む必要があり最短距離では到達できないため、いったん南に戻るか東に戻って回り道をする必要がある。最短経路数は0通り

* よってO→B→A→Pの経路数は0通り

* よってAとBの両方を通る経路は0通り

3. 最終的な答え

(1) 24通り

(2) 36通り

(3) 0通り