右図のような道路のある町で、A地点からB地点まで最短経路で行くとき、以下の問いに答える。 (1) A地点からB地点までの最短経路は何通りあるか。 (2) A地点からB地点まで、C地点を通る最短経路は何通りあるか。
2025/6/27
1. 問題の内容
右図のような道路のある町で、A地点からB地点まで最短経路で行くとき、以下の問いに答える。
(1) A地点からB地点までの最短経路は何通りあるか。
(2) A地点からB地点まで、C地点を通る最短経路は何通りあるか。
2. 解き方の手順
(1) A地点からB地点まで行くには、右に6回、上に3回移動する必要がある。したがって、最短経路の総数は、9回の移動のうち、右方向への移動6回を選ぶ組み合わせの数である。これは組み合わせの公式で計算できる。
\binom{9}{6} = \frac{9!}{6!3!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 3 \times 4 \times 7 = 84
(2) A地点からC地点までの最短経路は、右に3回、上に2回移動する必要がある。
その経路数は、5回の移動のうち、右方向への移動3回を選ぶ組み合わせの数である。
\binom{5}{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10
C地点からB地点までの最短経路は、右に3回、上に1回移動する必要がある。
その経路数は、4回の移動のうち、右方向への移動3回を選ぶ組み合わせの数である。
\binom{4}{3} = \frac{4!}{3!1!} = \frac{4}{1} = 4
したがって、A地点からC地点を経由してB地点まで行く最短経路数は、A地点からC地点までの経路数と、C地点からB地点までの経路数の積で求められる。
3. 最終的な答え
(1) A地点からB地点までの最短経路は84通り。
(2) A地点からB地点まで、C地点を通る最短経路は40通り。