格子状の道路網において、A地点からB地点へ最短経路で行く場合の数を求める問題です。以下の4つの場合について、経路数を求めます。 (1) Dを通る経路 (2) Cを通らずDを通る経路 (3) CまたはDを通る経路 (4) C, Dともに通らない経路

1. 問題の内容

格子状の道路網において、A地点からB地点へ最短経路で行く場合の数を求める問題です。以下の4つの場合について、経路数を求めます。

(1) Dを通る経路

(2) Cを通らずDを通る経路

(3) CまたはDを通る経路

(4) C, Dともに通らない経路

2. 解き方の手順

まず、A地点からB地点への最短経路の総数を求めます。

次に、各場合について経路数を求めます。

(1) Dを通る経路

AからDへの経路数と、DからBへの経路数をそれぞれ求め、掛け合わせます。

AからDへは、右に2回、上に1回移動するので、経路数は ${3 \choose 1} = 3$通りです。

DからBへは、右に1回、上に2回移動するので、経路数は ${3 \choose 1} = 3$通りです。

よって、Dを通る経路数は $3 \times 3 = 9$通りです。

(2) Cを通らずDを通る経路

Dを通る経路数から、CもDも通る経路数を引きます。

CとDを通る経路数は、AからCへの経路数と、CからDへの経路数と、DからBへの経路数を掛け合わせます。

AからCへは、右に1回、上に2回移動するので、経路数は ${3 \choose 1} = 3$通りです。

CからDへは、右に1回、上に-1回移動するので経路数は1通りです。

DからBへは、右に1回、上に2回移動するので、経路数は ${3 \choose 1} = 3$通りです。

よって、CとDを通る経路数は $3 \times 1 \times 3 = 9$通りです。

したがって、Cを通らずDを通る経路数は $9 - 9 = 0$通りです。

(3) CまたはDを通る経路

Cを通る経路数とDを通る経路数を足し合わせ、CとDの両方を通る経路数を引きます。

Dを通る経路数は(1)より9通りです。

AからBまでの経路総数は ${6 \choose 3} = 20$通りです。

AからCへは、右に1回、上に2回移動するので、経路数は ${3 \choose 1} = 3$通りです。

CからBへは、右に2回、上に1回移動するので、経路数は ${3 \choose 1} = 3$通りです。

よって、Cを通る経路数は $3 \times 3 = 9$通りです。

CまたはDを通る経路数は $9 + 9 - 9 = 9$通りです。

(4) C, Dともに通らない経路

AからBへの経路総数から、CまたはDを通る経路数を引きます。

AからBへの経路総数は ${6 \choose 3} = 20$通りです。

CまたはDを通る経路数は(3)より9通りです。

したがって、C, Dともに通らない経路数は $20 - 9 = 11$通りです。

3. 最終的な答え

(1) Dを通る経路：9通り

(2) Cを通らずDを通る経路：0通り

(3) CまたはDを通る経路：9通り

(4) C, Dともに通らない経路：11通り