右の図のような道のある町で、AからBまでの最短経路の総数、最短経路のうちQを通るものの総数、PまたはQを通るものの総数を求める問題です。

1. 問題の内容

右の図のような道のある町で、AからBまでの最短経路の総数、最短経路のうちQを通るものの総数、PまたはQを通るものの総数を求める問題です。

2. 解き方の手順

(1) AからBまでの最短経路の総数

AからBまでの最短経路は、右に4回、上に3回進む経路です。

したがって、最短経路の総数は、7回の移動のうち右に進む4回を選ぶ組み合わせの数で計算できます。

$${}_{7}C_{4} = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$$

よって、AからBまでの最短経路の総数は35通りです。

(2) AからQを通ってBまでの最短経路の総数

AからQまでの最短経路は、右に3回、上に1回進む経路です。

したがって、AからQまでの最短経路の総数は、4回の移動のうち右に進む3回を選ぶ組み合わせの数で計算できます。

$${}_{4}C_{3} = \frac{4!}{3!1!} = 4$$

QからBまでの最短経路は、右に1回、上に2回進む経路です。

したがって、QからBまでの最短経路の総数は、3回の移動のうち右に進む1回を選ぶ組み合わせの数で計算できます。

$${}_{3}C_{1} = \frac{3!}{1!2!} = 3$$

AからQを通ってBまでの最短経路の総数は、AからQまでの最短経路の総数とQからBまでの最短経路の総数の積で計算できます。

$4 \times 3 = 12$

よって、AからQを通ってBまでの最短経路の総数は12通りです。

(3) AからPを通ってBまでの最短経路の総数

AからPまでの最短経路は、右に2回、上に1回進む経路です。

したがって、AからPまでの最短経路の総数は、3回の移動のうち右に進む2回を選ぶ組み合わせの数で計算できます。

$${}_{3}C_{2} = \frac{3!}{2!1!} = 3$$

PからBまでの最短経路は、右に2回、上に2回進む経路です。

したがって、PからBまでの最短経路の総数は、4回の移動のうち右に進む2回を選ぶ組み合わせの数で計算できます。

$${}_{4}C_{2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$$

AからPを通ってBまでの最短経路の総数は、AからPまでの最短経路の総数とPからBまでの最短経路の総数の積で計算できます。

$3 \times 6 = 18$

よって、AからPを通ってBまでの最短経路の総数は18通りです。

(4) AからPもQも通ってBまでの最短経路の総数

AからPまでの最短経路は、右に2回、上に1回進む経路です。

したがって、AからPまでの最短経路の総数は3通りです。

PからQまでの最短経路は、右に1回、上に1回進む経路です。

したがって、PからQまでの最短経路の総数は2通りです。

QからBまでの最短経路は、右に1回、上に2回進む経路です。

したがって、QからBまでの最短経路の総数は3通りです。

AからPもQも通ってBまでの最短経路の総数は、

$3 \times 2 \times 3 = 18$通り

(5) PまたはQを通る最短経路の総数

PまたはQを通る経路の総数は、Pを通る経路の総数 + Qを通る経路の総数 - PとQ両方を通る経路の総数で求められます。

$18 + 12 - 18 = 12$

3. 最終的な答え

セソタ: 35

チツ: 12

テト: 12