南北に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. 解き方の手順

まず、O地点からA地点、O地点からB地点、A地点からP地点、B地点からP地点への最短経路の数を数えます。

図が無いと正確な位置関係がわからないため、以下のような位置関係を仮定して解きます。

O(0,0), A(2,2), B(4,1), P(5,6)

CはA,Bどちらでもない場所にあると仮定します。

(1) OからAへの経路は、右に2回、上に2回進むので、$_4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通り。

AからPへの経路は、右に3回、上に4回進むので、$_7C_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への経路は、右に4回、上に1回進むので、$_5C_1 = \frac{5!}{4!1!} = 5$通り。

BからPへの経路は、右に1回、上に5回進むので、$_6C_1 = \frac{6!}{5!1!} = 6$通り。

したがって、OからBを経由してPへ行く経路は$5 \times 6 = 30$通り。

(3) AとBの両方を通る最短経路は、OからAに行き、AからBに行き、BからPに行く経路と、OからBに行き、BからAに行き、AからPに行く経路の2通りが考えられます。ただし、AからB、BからAへ行く経路は最短経路とは限りません。問題文に同じ道を何度通っても良いとあるので、この解釈で良いと思われます。

OからAを経由してPへ行く経路は210通り。

OからBを経由してPへ行く経路は30通り。

A地点とB地点の両方を通る最短経路数は、OからA、AからB、BからPの経路数とOからB、BからA、AからPの経路数を考える必要があります。

OからAへは6通り。AからBへは右に2, 下に1なので3通り。BからPは6通り。したがって $6 \times 3 \times 6=108$通り

OからBへは5通り。BからAへは左に2, 上に1なので3通り。AからPは35通り。したがって $5 \times 3 \times 35=525$通り

合計は $108+525=633$通り

3. 最終的な答え

(1) 210通り

(2) 30通り

(3) 633通り