トップ› 京都大学› 2008年› 理系第2問（乙）

京都大学 2008年理系第2問（乙）解説

方針・初手

点 $P$ は時刻 $0$ においてすでに頂点 $A$ に位置しているため、「時刻 $0$ から時刻 $n$ までの間に $4$ 頂点すべてに現れる」という事象は、「時刻 $1$ から時刻 $n$ までの間に頂点 $B, C, D$ のすべてに少なくとも $1$ 回は現れる」という事象と同値です。直接この確率を求めるかわりに、余事象である「$B, C, D$ のうち少なくとも $1$ つの頂点に一度も現れない」確率を求め、全体から引く方針をとります。複数の条件の「少なくとも $1$ つ」を扱うため、包含排斥の原理が有効です。

解法1

点 $P$ の $1$ 秒ごとの移動の選択肢は常に $3$ 通りであるから、時刻 $1$ から時刻 $n$ までの $n$ 回の移動の経路は全部で $3^n$ 通りあり、これらはすべて等確率で起こる。

事象 $E_B$ を「時刻 $1$ から時刻 $n$ までの間に一度も頂点 $B$ に現れない」事象とする。同様に、事象 $E_C, E_D$ をそれぞれ「一度も頂点 $C$ に現れない」「一度も頂点 $D$ に現れない」事象とする。求める確率は $1 - P(E_B \cup E_C \cup E_D)$ である。

包含排斥の原理より、

$$ P(E_B \cup E_C \cup E_D) = P(E_B) + P(E_C) + P(E_D) - \{P(E_B \cap E_C) + P(E_C \cap E_D) + P(E_D \cap E_B)\} + P(E_B \cap E_C \cap E_D) $$

が成り立つ。対称性より、以下の各確率を求めればよい。

(i) $P(E_B)$ について

点 $P$ が頂点 $B$ 以外の $3$ 頂点（$A, C, D$）のみを移動し続ける確率である。このとき、各時刻での移動の選択肢は常に $2$ 通り（現在いる頂点以外の $2$ 頂点）となる。よって、そのような経路は $2^n$ 通りあり、

$$ P(E_B) = \frac{2^n}{3^n} = \left(\frac{2}{3}\right)^n $$

対称性から、$P(E_C) = P(E_D) = \left(\dfrac{2}{3}\right)^n$

(ii) $P(E_B \cap E_C)$ について

点 $P$ が頂点 $B, C$ の両方に一度も現れない、すなわち頂点 $A, D$ の $2$ 頂点のみを移動し続ける確率である。このとき、各時刻での移動の選択肢は常に $1$ 通り（$A$ からは $D$ へ、$D$ からは $A$ へ）となる。よって、そのような経路は $1^n = 1$ 通りあり、

$$ P(E_B \cap E_C) = \frac{1}{3^n} = \left(\frac{1}{3}\right)^n $$

対称性から、$P(E_C \cap E_D) = P(E_D \cap E_B) = \left(\dfrac{1}{3}\right)^n$

(iii) $P(E_B \cap E_C \cap E_D)$ について

点 $P$ が頂点 $B, C, D$ のいずれにも現れない、すなわち頂点 $A$ のみに留まり続ける確率である。しかし、毎秒必ず他の頂点へ移動しなければならないため、$n \geqq 1$ においてそのような移動は不可能である。よって、

$$ P(E_B \cap E_C \cap E_D) = 0 $$

以上より、

$$ P(E_B \cup E_C \cup E_D) = 3 \times \left(\frac{2}{3}\right)^n - 3 \times \left(\frac{1}{3}\right)^n $$

したがって、求める確率は

$$ 1 - P(E_B \cup E_C \cup E_D) = 1 - 3\left(\frac{2}{3}\right)^n + 3\left(\frac{1}{3}\right)^n $$

解説

「すべての状態を経由する確率」を求める典型問題です。これを真正面から漸化式などで解こうとすると、「現在どの頂点にいるか」だけでなく「これまでにいくつの頂点を訪問済みか」で状態を分ける必要があり、非常に複雑な連立漸化式になってしまいます。「すべての〇〇が起きる」＝「〇〇が起きないものがない」と言い換えることで、余事象を利用して簡潔に解くことができます。その際、複数の事象の和事象の確率を計算するために「包含排斥の原理（ベン図の拡張）」を用いるのが定石の処理です。