右のような道路がある町において、以下の条件でPからQまで最短経路で行く方法が何通りあるかを求める問題です。 (1) PからQまで行く (2) PからRを通ってQまで行く (3) Pから×印の箇所は通らずにQまで行く (4) PからRを通り、×印の箇所は通らずにQまで行く
2025/7/3
1. 問題の内容
右のような道路がある町において、以下の条件でPからQまで最短経路で行く方法が何通りあるかを求める問題です。
(1) PからQまで行く
(2) PからRを通ってQまで行く
(3) Pから×印の箇所は通らずにQまで行く
(4) PからRを通り、×印の箇所は通らずにQまで行く
2. 解き方の手順
(1) PからQまで行く
PからQまで行くには、右に5回、下に4回移動する必要があります。したがって、全部で9回の移動のうち、右への移動を5回選ぶ組み合わせの数を計算します。
これは組み合わせの公式を用いて で計算できます。
(2) PからRを通ってQまで行く
まず、PからRまで行く経路数を計算します。PからRまで行くには、右に1回、下に1回移動する必要があります。したがって、全部で2回の移動のうち、右への移動を1回選ぶ組み合わせの数を計算します。
これは組み合わせの公式を用いて で計算できます。
次に、RからQまで行く経路数を計算します。RからQまで行くには、右に4回、下に3回移動する必要があります。したがって、全部で7回の移動のうち、右への移動を4回選ぶ組み合わせの数を計算します。
これは組み合わせの公式を用いて で計算できます。
したがって、PからRを通ってQまで行く経路数は
(3) Pから×印の箇所は通らずにQまで行く
まず、PからQまでの経路数((1)で求めた値)を計算します。
次に、Pから×印を通ってQまで行く経路数を計算します。Pから×印まで行く経路数は、右に2回、下に1回移動する必要があります。したがって、全部で3回の移動のうち、右への移動を2回選ぶ組み合わせの数を計算します。
これは組み合わせの公式を用いて で計算できます。
次に、×印からQまで行く経路数を計算します。×印からQまで行くには、右に3回、下に3回移動する必要があります。したがって、全部で6回の移動のうち、右への移動を3回選ぶ組み合わせの数を計算します。
これは組み合わせの公式を用いて で計算できます。
したがって、Pから×印を通ってQまで行く経路数は
Pから×印を通らずにQまで行く経路数は、PからQまで行く経路数からPから×印を通ってQまで行く経路数を引いたものです。
(4) PからRを通り、×印の箇所は通らずにQまで行く
まず、PからRを通ってQまで行く経路数((2)で求めた値)を計算します。
次に、PからRを通り、かつ×印を通ってQまで行く経路数を計算します。これは、PからRに行く経路数()と、Rから×印に行く経路数()と、×印からQに行く経路数()を掛け合わせます。つまり、です。
したがって、PからRを通り、×印を通らずにQまで行く経路数は、
3. 最終的な答え
(1) 126通り
(2) 70通り
(3) 66通り
(4) 30通り