右の図のような道がある街において、以下の問いに答えます。 (1) AからBへ行く最短経路は何通りあるか。 (2) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。 (3) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。
2025/7/3
1. 問題の内容
右の図のような道がある街において、以下の問いに答えます。
(1) AからBへ行く最短経路は何通りあるか。
(2) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。
(3) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。
2. 解き方の手順
(1) AからBへ行く最短経路
AからBへ行くには、右に5回、上に4回移動する必要があります。
したがって、最短経路の総数は、9回の移動のうち、右への移動5回を選ぶ組み合わせの数に等しくなります。これは二項係数で表すことができ、
通りです。
(2) Cを通る経路
AからCへ行くには、右に2回、上に1回移動する必要があります。その経路数は
通りです。
CからBへ行くには、右に3回、上に3回移動する必要があります。その経路数は
通りです。
したがって、AからCを経由してBへ行く経路数は、 通りです。
(3) Cを通りDを通らない経路
まず、Cを通る経路の総数は60通りでした。
次に、Cを通り、かつDも通る経路の数を求めます。
CからDへ行くには、右に1回、上に2回移動する必要があります。その経路数は
通りです。
DからBへ行くには、右に2回、上に1回移動する必要があります。その経路数は
通りです。
したがって、AからCを経由し、Dも経由してBへ行く経路数は、 通りです。
Cを通り、Dを通らない経路数は、Cを通る経路の総数からCを通りDも通る経路数を引けばよいので、 通りです。
3. 最終的な答え
(1) AからBへ行く最短経路は 126 通り。
(2) AからBへ行く最短経路のうち、Cを通るものは 60 通り。
(3) AからBへ行く最短経路のうち、Cを通りDを通らないものは 33 通り。