図のような道がある街で、以下の3つの最短経路の数を求める問題です。 (1) AからBへ行く最短経路 (2) AからBへ行く最短経路のうち、Cを通るもの (3) AからBへ行く最短経路のうち、Cを通りDを通らないもの
2025/7/2
1. 問題の内容
図のような道がある街で、以下の3つの最短経路の数を求める問題です。
(1) AからBへ行く最短経路
(2) AからBへ行く最短経路のうち、Cを通るもの
(3) AからBへ行く最短経路のうち、Cを通りDを通らないもの
2. 解き方の手順
(1) AからBへの最短経路
AからBへ行くには、右に5マス、上に3マス進む必要があります。したがって、全部で8マス進むうち、右に5マス進む方向の選び方を考えればよいので、
通り
(2) AからBへの最短経路のうち、Cを通るもの
AからCへの最短経路は、右に2マス、上に1マス進むので、
通り
CからBへの最短経路は、右に3マス、上に2マス進むので、
通り
したがって、AからCを通ってBへ行く最短経路は、
通り
(3) AからBへの最短経路のうち、Cを通りDを通らないもの
AからCへは3通り。CからDへの最短経路は右に1マス、上に1マス進むので、
通り。DからBへの最短経路は右に2マス、上に1マス進むので、
通り。
したがって、AからCを通りDを通ってBへ行く最短経路は、
通り
Cを通る経路が30通りあり、そのうちDを通る経路が18通りあるので、Cを通りDを通らない経路は、
通り
3. 最終的な答え
(1) AからBへ行く最短経路は 56 通り
(2) AからBへ行く最短経路のうち、Cを通るものは 30 通り
(3) AからBへ行く最短経路のうち、Cを通りDを通らないものは 12 通り