右の図のような道がある街において、以下の3つの問いに答える。 (ア) AからBへ行く最短経路は何通りあるか。 (イ) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。 (ウ) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。
2025/7/3
1. 問題の内容
右の図のような道がある街において、以下の3つの問いに答える。
(ア) AからBへ行く最短経路は何通りあるか。
(イ) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。
(ウ) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。
2. 解き方の手順
(ア) AからBへの最短経路
AからBへ行くには、右に5回、上に3回移動する必要がある。したがって、最短経路の総数は、8回の移動のうち、右への移動を5回選ぶ組み合わせの数に等しい。これは、組み合わせの公式を用いて計算できる。
(イ) AからCを通ってBへ行く最短経路
AからCへ行くには、右に2回、上に1回移動する必要がある。その経路数は、通りである。
CからBへ行くには、右に3回、上に2回移動する必要がある。その経路数は、通りである。
したがって、AからCを通ってBへ行く最短経路数は、 通りである。
(ウ) AからCを通りDを通らずにBへ行く最短経路
AからCを通る経路は(イ)で30通りと求めた。
このうち、Dを通る経路を求める。
AからCを通りDを通る経路は、AからCまでの経路数(通り)とCからDまでの経路数(通り)とDからBまでの経路数(通り)を掛けて通りとなる。
したがって、AからCを通りDを通らない経路は、通りとなる。
3. 最終的な答え
(ア) 56通り
(イ) 30通り
(ウ) 12通り