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

(1) O地点からA地点まで最短で行く経路の数と、A地点からP地点まで最短で行く経路の数をそれぞれ計算し、それらを掛け合わせる。

OからAまで、右に2回、上に2回移動するので、経路数は$_{4}C_{2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通り。

AからPまで、右に1回、上に3回移動するので、経路数は$_{4}C_{1} = \frac{4!}{1!3!} = 4$通り。

したがって、O地点からA地点を経由してP地点へ最短距離で行く経路数は、$6 \times 4 = 24$通り。

(2) O地点からB地点まで最短で行く経路の数と、B地点からP地点まで最短で行く経路の数をそれぞれ計算し、それらを掛け合わせる。

OからBまで、右に2回、下に1回移動するので、経路数は$_{3}C_{2} = \frac{3!}{2!1!} = 3$通り。

BからPまで、右に1回、上に4回移動するので、経路数は$_{5}C_{1} = \frac{5!}{1!4!} = 5$通り。

したがって、O地点からB地点を経由してP地点へ最短距離で行く経路数は、$3 \times 5 = 15$通り。

(3) O地点から出発し、A地点とB地点の両方を通って、P地点へ最短距離で行く経路数を求める。

まず、A地点を経由してからB地点を経由する場合を考える。OからAへの経路数は6通り。(1)より。

AからBへ行く最短経路は存在しない。なぜならAよりBは南にあるから。AからBへ行くためには、一度南に下る必要があるが、そうするとPへの最短経路を通れない。よって、AからBを経由してPに行くことはできない。

次に、B地点を経由してからA地点を経由する場合を考える。OからBへの経路数は3通り。(2)より。

BからAへ行くためには、一度北へ移動してから西へ移動しなければならない。BからAへ行くためには、北に1回、西に1回移動すればよいので、経路数は$_{2}C_{1} = 2$通り。

AからPへの経路数は4通り。(1)より。

したがって、O地点からB地点を経由してA地点を経由してP地点へ最短距離で行く経路数は、$3 \times 2 \times 4 = 24$通り。

3. 最終的な答え

(1) 24通り

(2) 15通り

(3) 24通り