与えられた地図において、O地点からP地点まで最短距離で行く場合の道順の数を、以下の条件で求めます。 (1) O地点を出発し、A地点を通ってP地点へ行く道順の数 (2) O地点を出発し、B地点を通ってP地点へ行く道順の数 (3) O地点を出発し、A地点とB地点の両方を通ってP地点へ行く道順の数

1. 問題の内容

与えられた地図において、O地点からP地点まで最短距離で行く場合の道順の数を、以下の条件で求めます。

(1) O地点を出発し、A地点を通ってP地点へ行く道順の数

(2) O地点を出発し、B地点を通ってP地点へ行く道順の数

(3) O地点を出発し、A地点とB地点の両方を通ってP地点へ行く道順の数

2. 解き方の手順

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

OからAまでの最短経路は、右に2回、上に1回進むので、全部で3回の移動です。そのうち、右に2回進む場合の数は ${}_3 C_2 = 3$ 通りです。

AからPまでの最短経路は、右に4回、上に5回進むので、全部で9回の移動です。そのうち、右に4回進む場合の数は ${}_9 C_4 = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = 126$ 通りです。

よって、O地点を出発し、A地点を通り、P地点へ最短距離で行く道順は $3 \times 126 = 378$ 通りです。

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

OからBまでの最短経路は、右に1回、下に2回進むので、全部で3回の移動です。そのうち、右に1回進む場合の数は ${}_3 C_1 = 3$ 通りです。

BからPまでの最短経路は、右に5回、上に7回進むので、全部で12回の移動です。そのうち、右に5回進む場合の数は ${}_{12} C_5 = \frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 792$ 通りです。

よって、O地点を出発し、B地点を通り、P地点へ最短距離で行く道順は $3 \times 792 = 2376$ 通りです。

(3) O地点からA地点へ行き、A地点からB地点へ行き、B地点からP地点へ行く経路を考えます。AからBへはCを通れないため、AからBへの最短経路は存在しません。従ってA,B両方を通って最短距離でPにたどり着くことはできません。もしAB両方を通る場合は最短経路ではなくなるため、Aを通ってからBを通る場合と、Bを通ってからAを通る場合の両方考え、AB両方を通る場合は最短経路を考えることはできません。

ただし、問題文に「同じ道を何度通ってもよいとする」とあるので、最短経路という条件を無視すれば解釈可能です。

まず、OからAへの最短経路の数は3通り。（(1)より）

次に、AからBへの最短経路ではない経路の数を考えます。A地点の座標は(2,1)で、B地点の座標は(1,3)です。C地点を通れないので、迂回するしかありません。

最短経路ではないため、AB間をどのような経路を通っても構いません。よって、ここでは単純にAからBへの経路数を計算することはできません。

またBからPへの経路の数も同様に792通りです。

しかし、C地点は通れないという条件があるため、A地点とB地点の両方を通って最短距離で行く経路は存在しないと考えられます。

A地点からB地点へ最短経路で移動することは不可能であるため、A地点とB地点の両方を通ってP地点へ最短距離で行く経路は0通りです。

3. 最終的な答え

(1) 378通り

(2) 2376通り

(3) 0通り