格子状の道路網におけるA地点からB地点への最短経路について、以下の問いに答える問題です。 (1) 全ての経路の数 (2) P地点を通る経路の数 (3) P地点もQ地点も通らない経路の数 (4) 曲がる回数が3回の経路の数 (5) 南に進めず、後戻りできない場合のA地点からB地点への経路の数

1. 問題の内容

格子状の道路網におけるA地点からB地点への最短経路について、以下の問いに答える問題です。

(1) 全ての経路の数

(2) P地点を通る経路の数

(3) P地点もQ地点も通らない経路の数

(4) 曲がる回数が3回の経路の数

(5) 南に進めず、後戻りできない場合のA地点からB地点への経路の数

2. 解き方の手順

(1) 全ての経路の数

A地点からB地点まで、最短経路を進むためには、右に4回、上に3回進む必要があります。したがって、7回の移動のうち、右に進む4回を選ぶ組み合わせの数を求めればよいです。これは、組み合わせの公式 $C(n, k) = \frac{n!}{k!(n-k)!}$ を用いて計算できます。

$C(7, 4) = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通り

(2) P地点を通る経路の数

A地点からP地点まで、右に2回、上に1回進む必要があります。その経路の数は $C(3, 2) = \frac{3!}{2!1!} = 3$ 通りです。

P地点からB地点まで、右に2回、上に2回進む必要があります。その経路の数は $C(4, 2) = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通りです。

したがって、P地点を通る経路の数は $3 \times 6 = 18$ 通りです。

(3) P地点もQ地点も通らない経路の数

まず、全ての経路からP地点を通る経路を引きます。$35 - 18 = 17$ 通りです。

次に、Q地点を通る経路の数を求めます。

A地点からQ地点まで、右に1回、上に2回進む必要があります。その経路の数は $C(3, 1) = \frac{3!}{1!2!} = 3$ 通りです。

Q地点からB地点まで、右に3回、上に1回進む必要があります。その経路の数は $C(4, 3) = \frac{4!}{3!1!} = 4$ 通りです。

したがって、Q地点を通る経路の数は $3 \times 4 = 12$ 通りです。

ただし、P地点とQ地点の両方を通る経路を二重に引いているので、P地点とQ地点の両方を通る経路の数を足し戻す必要があります。

A地点からQ地点まで3通り、Q地点からP地点までは1通り、P地点からB地点までは6通りなので、P地点とQ地点の両方を通る経路は $3 \times 1 \times 6 = 18$ 通りあります。（QからPへ行くのは最短経路ではありません。）

Pを通る経路とQを通る経路を両方通る経路を差し引いて計算します。PもQも通らない経路の数 = (全体の経路数) - (Pを通る経路数) - (Qを通る経路数) + (PとQを両方通る経路数)。しかし、これは最短経路という条件に矛盾するため、この計算は誤りです。

包除原理を使うことを考えると、Pを通る経路とQを通る経路を両方通る経路の数は存在しません。

PもQも通らない経路の数 = (全体の経路数) - (Pを通る経路数) - (Qを通る経路数) $= 35 - 18 - 12 = 5$ 通り

(4) 曲がる回数が3回の経路の数

A地点からB地点までの最短経路は、右に4回、上に3回進む経路です。曲がる回数が3回であるということは、右と上の動きが交互に3回変わるということです。具体的には、「右上右上上」のようなパターンになります。

右、上をそれぞれR, Uと表すと、考えられるパターンは以下の通りです。

* RURURUUR, URURURUR

* RURURUU, URURURU

しかし、このような数え方では、AからBまで到達できない経路も含まれてしまいます。

AからBまでの最短経路は右4回、上3回なので、曲がる回数が3回になるのは以下の2パターンです。

RRRUUUU, UUUURRRR

上記のパターン数はそれぞれ1通りなので、合計2通りです。

しかし、A地点からB地点までの経路は右に4回、上に3回なので、曲がる回数は最大でも6回です。曲がる回数が3回であるためには、例えば「右、上、右、上、右、右、上」のような経路になります。

AからBへの最短経路で曲がる回数が3回となるのは、以下の2通りです。

「右上右上上」、「上右上右右」

(5) 南に進めず、後戻りできない場合のA地点からB地点への経路の数

この場合、A地点からB地点へは、右、上、東、北のいずれかに進むことしかできません。しかし、元の図は右に4マス、上に3マスなので、右と上のみを進む場合と変わりません。つまり、(1)と同じです。

したがって、35通りです。

3. 最終的な答え

(1) 35通り

(2) 18通り

(3) 5通り

(4) 2通り

(5) 35通り