碁盤の目状の道があり、O地点からP地点へ移動する際の最短経路の数を求める問題です。ただし、C地点は通ることができません。 (1) O地点からA地点を経由してP地点へ行く最短経路の数 (2) O地点からB地点を経由してP地点へ行く最短経路の数 (3) O地点からA地点とB地点の両方を経由してP地点へ行く最短経路の数

1. 問題の内容

碁盤の目状の道があり、O地点からP地点へ移動する際の最短経路の数を求める問題です。ただし、C地点は通ることができません。

(1) O地点からA地点を経由してP地点へ行く最短経路の数

(2) O地点からB地点を経由してP地点へ行く最短経路の数

(3) O地点からA地点とB地点の両方を経由してP地点へ行く最短経路の数

2. 解き方の手順

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

O地点からA地点へは、右に2回、上に2回移動する必要があります。したがって、最短経路の数は、

$\binom{4}{2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通りです。

A地点からP地点へは、右に4回、上に5回移動する必要があります。したがって、最短経路の数は、

$\binom{9}{4} = \frac{9!}{4!5!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$通りです。

したがって、O地点からA地点を経由してP地点へ行く最短経路の数は、

$6 \times 126 = 756$通りです。

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

O地点からB地点へは、右に1回、下に2回移動する必要があります。したがって、最短経路の数は、

$\binom{3}{1} = \frac{3!}{1!2!} = \frac{3}{1} = 3$通りです。

B地点からP地点へは、右に5回、上に7回移動する必要があります。したがって、最短経路の数は、

$\binom{12}{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$通りです。

したがって、O地点からB地点を経由してP地点へ行く最短経路の数は、

$3 \times 792 = 2376$通りです。

(3) O地点からA地点へ行き、A地点からB地点へ行くことはできないので、O地点からA地点を通って、次にB地点を通ってP地点に行くためには、A地点からB地点へ行かず、B地点へ直接行く必要がある。

O地点からA地点への最短経路の数は6通り。(1)より

A地点からP地点への最短経路の数は126通り。(1)より

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

B地点からP地点への最短経路の数は792通り。(2)より

O -> A -> P は756通り

O -> B -> P は2376通り

問題文に、A地点とB地点の両方を通ってとあるので、そのような経路は存在しない。

O地点からA地点を経由し、さらにB地点も経由してP地点へ行く最短経路を求める。AとBの間では最短経路は存在しないので、これは不可能である。

したがって、経路数は0通り。

3. 最終的な答え

(1) 756通り

(2) 2376通り

(3) 0通り