右の図のような碁盤の目状の道がある町で、PからQまで遠回りをせずに最短経路で行く。次の(1)~(3)の場合の道順の総数を求める。 (1) Rを通って行く場合 (2) ×印の箇所を通らないで行く場合 (3) Rを通り、×印の箇所を通らないで行く場合

## 問題11

1. 問題の内容

右の図のような碁盤の目状の道がある町で、PからQまで遠回りをせずに最短経路で行く。次の(1)~(3)の場合の道順の総数を求める。

(1) Rを通って行く場合

(2) ×印の箇所を通らないで行く場合

(3) Rを通り、×印の箇所を通らないで行く場合

2. 解き方の手順

(1) Rを通って行く場合

まず、PからRまでの最短経路の数を数える。これは右に2回、下に1回移動する経路なので、$_3C_2 = \frac{3!}{2!1!} = 3$通り。

次に、RからQまでの最短経路の数を数える。これは右に3回、下に3回移動する経路なので、$_6C_3 = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$通り。

したがって、PからRを通ってQまで行く最短経路の数は、$3 \times 20 = 60$通り。

(2) ×印の箇所を通らないで行く場合

まず、PからQまでのすべての最短経路の数を数える。これは右に5回、下に4回移動する経路なので、$_9C_5 = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$通り。

次に、×印の箇所を通る最短経路の数を数える。Pから×印の箇所までの最短経路の数は、右に3回、下に2回移動する経路なので、$_5C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$通り。×印の箇所からQまでの最短経路の数は、右に2回、下に2回移動する経路なので、$_4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通り。したがって、Pから×印の箇所を通ってQまで行く最短経路の数は、$10 \times 6 = 60$通り。

×印の箇所を通らない最短経路の数は、すべての最短経路の数から×印の箇所を通る最短経路の数を引けばよいので、$126 - 60 = 66$通り。

(3) Rを通り、×印の箇所を通らないで行く場合

Rを通る経路は(1)で60通りと求めた。このうち×印の箇所を通る経路の数を求め、60から引けばよい。

PからRまでの経路は3通り。Rから×印までの経路は1通り。×印からQまでの経路は6通り。したがって、PからRを通り、×印を通ってQまで行く最短経路の数は、$3 \times 1 \times 6 = 18$通り。

Rを通り、×印の箇所を通らない最短経路の数は、$60 - 18 = 42$通り。

3. 最終的な答え

(1) 60通り

(2) 66通り

(3) 42通り

## 問題12

1. 問題の内容

右の図のような碁盤の目状の道がある町で、AからBまで遠回りをせずに最短経路で行く。次の(1)~(4)の場合の道順の総数を求める。

(1) 全部の道順

(2) 地点Cを通る場合

(3) 地点Pを通らない場合

(4) 地点Pも地点Qも通らない場合

2. 解き方の手順

(1) 全部の道順

AからBまでの最短経路の数は、右に4回、上に3回移動する経路なので、$_7C_4 = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$通り。

(2) 地点Cを通る場合

AからCまでの最短経路の数は、右に1回、上に1回移動する経路なので、$_2C_1 = \frac{2!}{1!1!} = 2$通り。CからBまでの最短経路の数は、右に3回、上に2回移動する経路なので、$_5C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$通り。したがって、AからCを通ってBまで行く最短経路の数は、$2 \times 10 = 20$通り。

(3) 地点Pを通らない場合

AからPまでの最短経路の数は、右に2回、上に2回移動する経路なので、$_4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通り。PからBまでの最短経路の数は、右に2回、上に1回移動する経路なので、$_3C_2 = \frac{3!}{2!1!} = 3$通り。したがって、AからPを通ってBまで行く最短経路の数は、$6 \times 3 = 18$通り。

Pを通らない最短経路の数は、すべての最短経路の数からPを通る最短経路の数を引けばよいので、$35 - 18 = 17$通り。

(4) 地点Pも地点Qも通らない場合

まず、地点Pを通る経路は18通りと求めた。次に、地点Qを通る経路の数を求める。

AからQまでの最短経路の数は、右に3回、上に3回移動する経路なので、$_6C_3 = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$通り。QからBまでの最短経路の数は、右に1回、上に0回移動する経路なので、$_1C_1 = 1$通り。したがって、AからQを通ってBまで行く最短経路の数は、$20 \times 1 = 20$通り。

地点PとQの両方を通る経路の数を求める。AからPまでの経路は6通り。PからQまでの最短経路の数は、右に1回、上に1回移動する経路なので、$_2C_1 = 2$通り。QからBまでの経路は1通り。したがって、AからPを通ってQを通ってBまで行く最短経路の数は、$6 \times 2 \times 1 = 12$通り。

地点PまたはQを通る経路の数は、$18 + 20 - 12 = 26$通り。

したがって、地点Pも地点Qも通らない最短経路の数は、$35 - 26 = 9$通り。

3. 最終的な答え

(1) 35通り

(2) 20通り

(3) 17通り

(4) 9通り