図のような格子状の道において、点Pから点Qまで最短経路で行く方法について、以下の3つの場合の数を求める問題です。 (1) PからQまでの最短経路の総数 (2) PからQまでの最短経路のうち、点Rと点Sの両方を通る経路の数 (3) PからQまでの最短経路のうち、×印の箇所を通らない経路の数
2025/7/14
1. 問題の内容
図のような格子状の道において、点Pから点Qまで最短経路で行く方法について、以下の3つの場合の数を求める問題です。
(1) PからQまでの最短経路の総数
(2) PからQまでの最短経路のうち、点Rと点Sの両方を通る経路の数
(3) PからQまでの最短経路のうち、×印の箇所を通らない経路の数
2. 解き方の手順
(1) PからQまでの最短経路の総数
PからQまで、右に6マス、下に4マス進む必要があります。したがって、合計10回の移動のうち、右に移動する6回を選べば経路が一意に決まります。これは組み合わせの問題として解けます。総経路数は で計算できます。
(2) PからQまでの最短経路のうち、点Rと点Sの両方を通る経路の数
PからRまでの最短経路数、RからSまでの最短経路数、SからQまでの最短経路数をそれぞれ求め、それらを掛け合わせます。
- PからRまで:右に2マス、下に1マスなので、 通り
- RからSまで:右に0マス、下に2マスなので、 通り
- SからQまで:右に4マス、下に1マスなので、 通り
したがって、RとSをともに通る経路数は 通りです。
(3) PからQまでの最短経路のうち、×印の箇所を通らない経路の数
まず、PからQまでのすべての経路数から、×印の箇所を通る経路数を引きます。
Pから×印の箇所までの最短経路数は、右に3マス、下に1マスなので、 通りです。
×印の箇所からQまでの最短経路数は、右に3マス、下に3マスなので、 通りです。
したがって、×印の箇所を通る経路数は 通りです。
したがって、×印の箇所を通らない経路数は 通りです。
3. 最終的な答え
(1) 210通り
(2) 15通り
(3) 130通り