トップ› 北海道大学› 1999年› 理系第2問

北海道大学 1999年理系第2問解説

注意画像の一部が不鮮明で、特に図3の $a, b$ の通行止め箇所の読取りに不確実性があります。以下は、出発点 $S$ を座標 $(0,0)$ としたとき、「$a$ を $(1,1)$ と $(1,2)$ を結ぶ道、$b$ を $(4,3)$ と $(5,3)$ を結ぶ道」として解釈した場合の解答解説です。

方針・初手

各地点を座標で表すことで、移動の組合せとして経路数を計算する。 $S$ を原点 $(0,0)$ とし、東方向を $x$ 軸の正の向き、北方向を $y$ 軸の正の向きとする。1区画の移動を1とすると、$G$ の座標は $(7,4)$ となる。最短経路の数は、東西方向と南北方向の移動回数を用いた同じものを含む順列（または組合せ）で求められる。通行止めがある場合は、余事象の考え方と包除原理を利用して、全体から通れない経路を引く方針を取る。

解法1

(1) $S(0,0)$ から $G(7,4)$ に到達するには、東に7区画、北に4区画、合計11区画進む必要がある。求める経路の総数は、11回の移動のうち北へ進む4回の選び方と等しいので

$$ \frac{11!}{7!4!} = 330 $$

(2) 図2より、各地点の座標は $A(1,1)$、$B(2,1)$ となる。求める経路は、$S \to A \to B \to G$ の順に進む経路である。 $S(0,0)$ から $A(1,1)$ への経路数は

$$ \frac{2!}{1!1!} = 2 $$

$A(1,1)$ から $B(2,1)$ への経路数は $1$ 通りである。 $B(2,1)$ から $G(7,4)$ への経路数は、東に5区画、北に3区画進むので

$$ \frac{8!}{5!3!} = 56 $$

よって、求める経路数はこれらを掛け合わせて

$$ 2 \times 1 \times 56 = 112 $$

(3) 図3の通行止め箇所について、前述の座標設定より $a$ は点 $(1,1)$ と $(1,2)$ を結ぶ道、$b$ は点 $(4,3)$ と $(5,3)$ を結ぶ道である。事象 $A$ を「道 $a$ を通る」、事象 $B$ を「道 $b$ を通る」とする。求める経路数は、全経路数から道 $a, b$ の少なくとも一方を通る経路数を引いたものであり、包除原理を用いると全体の経路数から $n(A \cup B)$ を引けばよい。

$$ n(A \cup B) = n(A) + n(B) - n(A \cap B) $$

(i) 道 $a$ を通る経路数 $n(A)$ $S \to (1,1) \to (1,2) \to G$ と進む経路数である。

$$ \frac{2!}{1!1!} \times 1 \times \frac{8!}{6!2!} = 2 \times 1 \times 28 = 56 $$

(ii) 道 $b$ を通る経路数 $n(B)$ $S \to (4,3) \to (5,3) \to G$ と進む経路数である。

$$ \frac{7!}{4!3!} \times 1 \times \frac{3!}{2!1!} = 35 \times 1 \times 3 = 105 $$

(iii) 道 $a, b$ をともに通る経路数 $n(A \cap B)$ $S \to (1,1) \to (1,2) \to (4,3) \to (5,3) \to G$ と進む経路数である。

$$ \frac{2!}{1!1!} \times 1 \times \frac{4!}{3!1!} \times 1 \times \frac{3!}{2!1!} = 2 \times 1 \times 4 \times 1 \times 3 = 24 $$

したがって、$a, b$ の少なくとも一方を通る経路数は

$$ n(A \cup B) = 56 + 105 - 24 = 137 $$

以上より、求める経路数は

$$ 330 - 137 = 193 $$

解説

最短経路問題における基本的な典型問題である。特定の「点」を通る場合はその点までの経路とそこからの経路を掛け合わせる。特定の「線分（道）」を通る・通らない場合は、その線分の両端の点を必ずその向きに通過するものとして経路を分割して考える。 (3) のように複数の通行止めや障害物がある場合は、「全体からダメなものを引く」という余事象の考え方が有効であり、重複して引いてしまう部分を足し戻す「包除原理」を正確に適用できるかがポイントとなる。