トップ› 京都大学› 2015年› 文系第3問

京都大学 2015年文系第3問解説

方針・初手

点 A から点 E に至る経路として考えられるものをすべて洗い出す。図より、同じ点を 2 度通らない経路は $\mathrm{A\text{-}F\text{-}E}$（長さ 2）、$\mathrm{A\text{-}B\text{-}E}$（長さ 2）、$\mathrm{A\text{-}B\text{-}C\text{-}D\text{-}E}$（長さ 4）の 3 つのみである。
最短の長さ $X$ が 2, 4 となる条件を、各線分が赤に塗られる事象を用いて表し、それぞれの確率を求める。
$X=0$ となる確率は、全確率 $1$ から $P(X=2)$ と $P(X=4)$ を引く余事象の考え方を用いて計算する。

解法1

図の 7 本の線分を次のように名付ける。

$$ e_1 = \mathrm{AF},\ e_2 = \mathrm{FE},\ e_3 = \mathrm{AB},\ e_4 = \mathrm{BE},\ e_5 = \mathrm{BC},\ e_6 = \mathrm{CD},\ e_7 = \mathrm{DE} $$

各線分が赤く塗られる確率はそれぞれ $\dfrac{1}{2}$ であり、互いに独立である。

点 A から点 E に至る経路（同じ点を 2 度通らないもの）は以下の 3 通りである。

経路 $R_1$: $\mathrm{A \to F \to E}$（長さ 2、使用線分 $e_1, e_2$）
経路 $R_2$: $\mathrm{A \to B \to E}$（長さ 2、使用線分 $e_3, e_4$）
経路 $R_3$: $\mathrm{A \to B \to C \to D \to E}$（長さ 4、使用線分 $e_3, e_5, e_6, e_7$）

(1) $X=2$ となる確率

最短経路の長さが 2 となるのは、経路 $R_1$ または $R_2$ が赤線のみで構成される場合である。

$$ A_1 = \{e_1 \text{ かつ } e_2 \text{ が赤}\}, \quad A_2 = \{e_3 \text{ かつ } e_4 \text{ が赤}\} $$

とおくと、求める確率は $P(A_1 \cup A_2)$ である。

$$ P(A_1) = \left(\frac{1}{2}\right)^2 = \frac{1}{4}, \quad P(A_2) = \left(\frac{1}{2}\right)^2 = \frac{1}{4} $$

$$ P(A_1 \cap A_2) = \left(\frac{1}{2}\right)^4 = \frac{1}{16} $$

$$ P(X=2) = P(A_1 \cup A_2) = \frac{1}{4} + \frac{1}{4} - \frac{1}{16} = \frac{7}{16} $$

(2) $X=4$ となる確率

最短経路の長さが 4 となるのは、長さ 2 の経路が存在せず、かつ長さ 4 の経路が赤線のみで構成される場合である。

$$ A_3 = \{e_3, e_5, e_6, e_7 \text{ がすべて赤}\} $$

とおく。$A_3$ が起こるという条件の下で、

$A_2$（$e_3, e_4$ が赤）が起こらないためには、$e_4$ が黒でなければならない。
$A_1$（$e_1, e_2$ が赤）が起こらないためには、$e_1, e_2$ の少なくとも一方が黒でなければならない。

これらに関わる線分の集合 $\{e_3, e_5, e_6, e_7\}$、$\{e_4\}$、$\{e_1, e_2\}$ は互いに素であるから、それぞれの事象は独立である。

$$ P(A_3) = \left(\frac{1}{2}\right)^4 = \frac{1}{16}, \quad P(e_4 \text{ が黒}) = \frac{1}{2}, \quad P(\overline{A_1}) = 1 - \frac{1}{4} = \frac{3}{4} $$

$$ P(X=4) = \frac{1}{16} \times \frac{1}{2} \times \frac{3}{4} = \frac{3}{128} $$

(3) $X=0$ となる確率

$X=0$ は A から E に至る赤のみの経路が存在しない場合である。

$$ P(X=0) = 1 - P(X=2) - P(X=4) = 1 - \frac{7}{16} - \frac{3}{128} = \frac{128 - 56 - 3}{128} = \frac{69}{128} $$

解説

与えられたネットワークにおける経路の存在確率を求める問題である。A から E までの経路のパターンが 3 種類しかないことに気づけば、それぞれの長さごとに事象を分割して確率を計算できる。

$X=2$ の場合は典型的な和事象の確率（包除原理）を用いる。$X=4$ の場合は「長さ 4 の経路は通れるが、長さ 2 の経路は通れない」という条件を正しく立式できるかがポイントである。長さ 4 の経路を構成する線分と、長さ 2 の経路を遮断するために必要な線分が互いに独立であることを確認してから積をとると、論理的な見通しが良くなる。

$X=0$ については、直接求めようとすると切断のパターン分けが煩雑になるため、余事象を利用して求めるのが定石である。