右の図のような道のある町で、A地点からB地点まで最短経路で行く方法について、以下の2つの場合についてその経路数を求める問題です。 (1) AからBまで行く最短経路の総数。 (2) AからCを通らずにBまで行く最短経路の総数。
2025/7/7
1. 問題の内容
右の図のような道のある町で、A地点からB地点まで最短経路で行く方法について、以下の2つの場合についてその経路数を求める問題です。
(1) AからBまで行く最短経路の総数。
(2) AからCを通らずにBまで行く最短経路の総数。
2. 解き方の手順
(1) AからBまで行く最短経路の総数
AからBまで行くには、右に6回、上に4回移動する必要があります。これは、10回の移動のうち、右への移動を6回選ぶ(または上への移動を4回選ぶ)組み合わせの数に等しいです。
したがって、経路数は以下のようになります。
(2) AからCを通らずにBまで行く最短経路の総数
まず、AからCまでの最短経路の数を求めます。AからCまでは、右に3回、上に2回移動する必要があります。経路数は通りです。
次に、CからBまでの最短経路の数を求めます。CからBまでは、右に3回、上に2回移動する必要があります。経路数は通りです。
AからCを通りBまで行く最短経路の総数は、AからCまでの経路数とCからBまでの経路数の積で求められます。
通り
AからBまでの最短経路の総数から、AからCを通りBまで行く最短経路の総数を引けば、AからCを通らずにBまで行く最短経路の総数が求められます。
通り
3. 最終的な答え
(1) AからBまで行く最短経路は210通り。
(2) AからCを通らずにBまで行く最短経路は110通り。