与えられた街路図において、AからBへ最短距離で行く方法の数を求める問題です。以下の3つの場合について考えます。 (1) AからBへ行く方法 (2) AからCを通ってBへ行く方法 (3) AからCを通らないでBへ行き、帰りはCを通ってAに帰る方法

1. 問題の内容

与えられた街路図において、AからBへ最短距離で行く方法の数を求める問題です。以下の3つの場合について考えます。

(1) AからBへ行く方法

(2) AからCを通ってBへ行く方法

(3) AからCを通らないでBへ行き、帰りはCを通ってAに帰る方法

2. 解き方の手順

(1) AからBへ行く方法

AからBへ最短距離で行くには、右に4回、下に3回移動する必要があります。

したがって、全体の移動回数は7回です。このうち、右への移動を4回選ぶ組み合わせの数を求めます。

これは、7回の移動のうち、右へ進む4回を選ぶ組み合わせなので、

${}_7 C_4 = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$通りです。

(2) AからCを通ってBへ行く方法

AからCへ行くには、右に2回、下に2回移動する必要があります。

この場合の移動回数は4回なので、

${}_4 C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通りです。

CからBへ行くには、右に2回、下に1回移動する必要があります。

この場合の移動回数は3回なので、

${}_3 C_2 = \frac{3!}{2!1!} = \frac{3 \times 2}{2 \times 1} = 3$通りです。

したがって、AからCを通ってBへ行く方法は、

$6 \times 3 = 18$通りです。

(3) AからCを通らないでBへ行き、帰りはCを通ってAに帰る方法

まず、AからBへ行くすべての方法(35通り)から、AからCを通ってBへ行く方法(18通り)を除きます。

$35 - 18 = 17$通り。

これは、AからCを通らないでBへ行く方法です。

次に、BからCを通ってAへ帰る方法を考えます。BからCへ行くには、上に1回、左に2回移動する必要があります。

したがって、${}_3 C_1=3$通りです。CからAへ行くには、上に2回、左に2回移動する必要があります。

したがって、${}_4 C_2=6$通りです。

BからCを通ってAへ行く方法は、 $3 \times 6 = 18$通りです。

したがって、AからCを通らないでBへ行き、帰りはCを通ってAに帰る方法は、$17 \times 18 = 306$通りです。

3. 最終的な答え

(1) 35通り

(2) 18通り

(3) 306通り