画像の問題16は、ある街の道路網が与えられ、点Aから点Bへ行く最短経路の数、点Cを通る最短経路の数、そして点Cを通り点Dを通らない最短経路の数を求める問題です。
2025/7/2
1. 問題の内容
画像の問題16は、ある街の道路網が与えられ、点Aから点Bへ行く最短経路の数、点Cを通る最短経路の数、そして点Cを通り点Dを通らない最短経路の数を求める問題です。
2. 解き方の手順
まず、AからBへの最短経路の総数を求めます。AからBへは、右に5回、上に3回移動する必要があります。したがって、8回の移動のうち、右への移動を5回選ぶ組み合わせの数が最短経路の総数となります。これは組み合わせの数 で計算できます。
次に、AからCを通ってBへ行く最短経路の数を求めます。AからCへは、右に2回、上に1回移動する必要があります。CからBへは、右に3回、上に2回移動する必要があります。AからCへの最短経路の数はであり、CからBへの最短経路の数はです。したがって、AからCを通ってBへ行く最短経路の数はです。
最後に、AからCを通るがDを通らない最短経路の数を求めます。AからCを通る経路数はすでに求めました。AからCを通ってDを通る経路数を計算し、それを全体の経路数から引けば、AからCを通りDを通らない経路数が求まります。AからCへの経路数はです。CからDへの経路数は右に1回、上に1回移動するのでです。DからBへの経路数は右に2回、上に1回移動するのでです。したがって、AからCを通ってDを通ってBに行く経路数はです。よって、AからCを通りDを通らない経路数は、です。
3. 最終的な答え
* AからBへ行く最短経路は 通り。
* そのうち、Cを通るものは30通り。
* また、AからBへ行く最短経路のうち、Cを通りDを通らないものは12通り。