図のように、南北に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地点を通り、P地点へ最短距離で行く道順の総数を求めます。

OからAへの最短経路数は、右に3回、上に1回移動する必要があるため、4回の移動のうち右を3回選ぶ組み合わせを考えます。

${}_4 C_3 = \frac{4!}{3!1!} = 4$

AからPへの最短経路数は、右に3回、上に5回移動する必要があるため、8回の移動のうち右を3回選ぶ組み合わせを考えます。

${}_8 C_3 = \frac{8!}{3!5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$

したがって、O地点を出発し、A地点を通り、P地点へ最短距離で行く道順の数は、

$4 \times 56 = 224$

(2) O地点からB地点への最短経路の数と、B地点からP地点への最短経路の数を求め、それらを掛け合わせることで、O地点を出発し、B地点を通り、P地点へ最短距離で行く道順の総数を求めます。

OからBへの最短経路数は、右に1回、下に2回移動する必要があるため、3回の移動のうち右を1回選ぶ組み合わせを考えます。

${}_3 C_1 = \frac{3!}{1!2!} = 3$

BからPへの最短経路数は、右に5回、上に7回移動する必要があるが、C地点を通ることができない。

まずはC地点を通れるとしたときの経路数を計算する。

${}_{12} C_5 = \frac{12!}{5!7!} = \frac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1} = 792$

次に、BからCへの経路数と、CからPへの経路数を求め、積を求めることで、BからPへCを通って行く経路数を求める。

BからCへの経路数は、右に4回、上に1回移動する必要があるため、5回の移動のうち右を4回選ぶ組み合わせを考えます。

${}_5 C_4 = \frac{5!}{4!1!} = 5$

CからPへの経路数は、右に1回、上に6回移動する必要があるため、7回の移動のうち右を1回選ぶ組み合わせを考えます。

${}_7 C_1 = \frac{7!}{1!6!} = 7$

したがって、BからPへCを通って行く経路数は、

$5 \times 7 = 35$

BからPへの最短経路数は、Cを通らない経路数であるため、

$792 - 35 = 757$

したがって、O地点を出発し、B地点を通り、P地点へ最短距離で行く道順の数は、

$3 \times 757 = 2271$

(3) OからAへ行き、AからBへ行き、BからPへ行く経路数を求めることはできない。

O地点からA地点への最短経路の数は4通り。

O地点からB地点への最短経路の数は3通り。

O地点からA地点を経由してP地点へ行く経路の数は224通り。

O地点からB地点を経由してP地点へ行く経路の数は2271通り。

最終的な答えが導き出せないため、解き方の手順は途中までとなります。

3. 最終的な答え

(1) 224通り

(2) 2271通り

(3) 解答不能