図のように、南北に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地点へ最短距離で行く道順は、右に2回、上に2回進む必要があるため、$_{4}C_{2} = \frac{4!}{2!2!} = 6$通り。

A地点からP地点へ最短距離で行く道順は、右に3回、上に5回進む必要があるため、$_{8}C_{3} = \frac{8!}{3!5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$通り。

したがって、O地点からA地点を通りP地点へ最短距離で行く道順は、$6 \times 56 = 336$通り。

(2) O地点からB地点へ最短距離で行く道順は、右に1回、下に3回進む必要があるため、$_{4}C_{1} = \frac{4!}{1!3!} = 4$通り。

B地点からP地点へ最短距離で行く道順は、右に4回、上に2回進む必要があるため、$_{6}C_{4} = \frac{6!}{4!2!} = \frac{6 \times 5}{2 \times 1} = 15$通り。

したがって、O地点からB地点を通りP地点へ最短距離で行く道順は、$4 \times 15 = 60$通り。

(3) O地点からA地点へ最短距離で行く道順は、(1)より6通り。A地点からB地点へ最短距離で行く道順は、右に-1回、下に5回進む必要があるため、存在しない。

O地点からB地点へ最短距離で行く道順は、(2)より4通り。B地点からA地点へ最短距離で行く道順は、右に2回、上に-3回進む必要があるため、存在しない。

AとBの両方を通る場合、A→BかB→Aのどちらかの順で通ることになります。

O→A→B→P　と　O→B→A→P の経路を考えます。

OからAまでの経路は(1)より6通りです。

AからBまでの経路は、最短経路では存在しません。同じ道を何度通っても良い、ということなので、AからBまで、右に1つ、下に1つ、下に1つ、下に1つと進む経路を考えます。この時、AからBへ行くためには、右方向に1回、下方向に3回移動する必要があります。経路の数としては、$_{4}C_1 = 4$通りとなります。

BからPまでの経路は(2)より15通りです。

したがって、O→A→B→P の経路数は、6 * 4 * 15 = 360通りとなります。

OからBまでの経路は(2)より4通りです。

BからAまでの経路は、最短経路では存在しません。同じ道を何度通っても良い、ということなので、BからAまで、左に1つ、上に1つ、上に1つ、上に1つと進む経路を考えます。この時、BからAへ行くためには、左方向に1回、上方向に3回移動する必要があります。経路の数としては、$_{4}C_1 = 4$通りとなります。

AからPまでの経路は(1)より56通りです。

したがって、O→B→A→P の経路数は、4 * 4 * 56 = 896通りとなります。

A地点とB地点の両方を通る経路の総数は、360 + 896 = 1256通りです。

3. 最終的な答え

(1) 336通り

(2) 60通り

(3) 1256通り