右図のような道路がある地域において、以下の問いに答えます。 (1) AからBまでの最短経路は何通りあるか。 (2) AからCを通ってBまでの最短経路は何通りあるか。 (3) AからCを通らずにBまでの最短経路は何通りあるか。

1. 問題の内容

右図のような道路がある地域において、以下の問いに答えます。

(1) AからBまでの最短経路は何通りあるか。

(2) AからCを通ってBまでの最短経路は何通りあるか。

(3) AからCを通らずにBまでの最短経路は何通りあるか。

2. 解き方の手順

(1) AからBまでの最短経路

AからBまで行くには、右に4回、上に2回移動する必要があります。

したがって、これは6回の移動のうち、どちらを上に移動するかを選ぶ組み合わせと同じです。

よって、AからBまでの最短経路は、

$_{6}C_{2} = \frac{6!}{2!(6-2)!} = \frac{6!}{2!4!} = \frac{6 \times 5}{2 \times 1} = 15$ 通りです。

(2) AからCを通ってBまでの最短経路

AからCまで行くには、右に2回、上に1回移動する必要があります。

AからCまでの最短経路は、$_{3}C_{1} = \frac{3!}{1!(3-1)!} = \frac{3!}{1!2!} = \frac{3 \times 2 \times 1}{1 \times 2 \times 1} = 3$ 通りです。

CからBまで行くには、右に2回、上に1回移動する必要があります。

CからBまでの最短経路は、$_{3}C_{1} = \frac{3!}{1!(3-1)!} = \frac{3!}{1!2!} = \frac{3 \times 2 \times 1}{1 \times 2 \times 1} = 3$ 通りです。

したがって、AからCを通ってBまでの最短経路は、$3 \times 3 = 9$ 通りです。

(3) AからCを通らずにBまでの最短経路

AからBまでの最短経路から、AからCを通ってBまでの最短経路を引けば、AからCを通らずにBまでの最短経路が求まります。

AからBまでの最短経路は15通り、AからCを通ってBまでの最短経路は9通りなので、AからCを通らずにBまでの最短経路は、$15 - 9 = 6$ 通りです。

3. 最終的な答え

(1) AからBまでの最短経路は 15 通り

(2) AからCを通ってBまでの最短経路は 9 通り

(3) AからCを通らずにBまでの最短経路は 6 通り