図のような道路のある町で、P地点からQ地点まで最短経路で行く場合の数を求める問題です。 (1) R地点を通る経路の総数 (2) ×印の地点を通らない経路の総数 (3) R地点を通り、かつ×印の地点を通らない経路の総数 をそれぞれ求めます。
2025/7/2
1. 問題の内容
図のような道路のある町で、P地点からQ地点まで最短経路で行く場合の数を求める問題です。
(1) R地点を通る経路の総数
(2) ×印の地点を通らない経路の総数
(3) R地点を通り、かつ×印の地点を通らない経路の総数
をそれぞれ求めます。
2. 解き方の手順
経路の総数は、右に進む回数と上に進む回数が決まれば一意に定まることを利用します。
(1) R地点を通る経路の総数
PからRまでの経路数と、RからQまでの経路数をそれぞれ求め、それらの積を計算します。
PからRまでは、右に2回、上に2回進むので、経路数は
RからQまでは、右に4回、上に4回進むので、経路数は
したがって、Rを通る経路の総数は
(2) ×印の箇所を通らない経路の総数
PからQまでの経路の総数を求め、次に×印を通る経路の総数を求め、それらを引くことで求めます。
PからQまでの経路の総数は、右に6回、上に6回進むので
次に、×印を通る経路の総数を求めます。
Pから×印までは、右に3回、上に2回進むので、経路数は
×印からQまでは、右に3回、上に4回進むので、経路数は
したがって、×印を通る経路の総数は
したがって、×印を通らない経路の総数は
(3) Rを通り、×印の箇所は通らない経路の総数
Rを通る経路の総数から、Rを通り、かつ×印を通る経路の総数を引くことで求めます。
Rを通り、かつ×印を通る経路の総数を求めます。
PからRまでは、右に2回、上に2回進むので、経路数は
Rから×印までは、右に1回進むので、経路数は1通り。
×印からQまでは、右に3回、上に4回進むので、経路数は
したがって、Rを通り、×印を通る経路の総数は
したがって、Rを通り、×印を通らない経路の総数は
3. 最終的な答え
(1) 420通り
(2) 574通り
(3) 210通り