2京都大学 2008年 数学 第2問解答・解説

時刻$0$では$A$にいるので、Aはすでに訪問済みである。$B,C,D$のうち少なくとも一つを訪れない事象について包除原理を用いる。

$B$を時刻$n$まで訪れない事象を$E_B$とする。$E_B$が起きている間、点$P$は$A,C,D$のいずれかにあり、次の移動先としてこの$3$頂点内に残る選択肢は常に$2$個である。各移動では全$3$候補が等確率なので $$\displaystyle P(E_B)=\left(\frac{2}{3}\right)^n.$$ 同様に、$B,C,D$の各$1$頂点を訪れない確率はそれぞれ$\displaystyle \left(\frac23\right)^n$である。

例えば$B,C$の両方を訪れない場合、$P$は$A$と$D$だけを動く。現在の頂点以外に許される移動先は$1$個だけだから、その確率は$\displaystyle \left(\frac13\right)^n$である。訪れない$2$頂点の選び方は3通りある。

$B,C,D$のすべてを訪れないことは、$n\ge1$なら最初の移動で$A$を離れるため不可能である。よって包除原理から $$\displaystyle P=1-\binom31\left(\frac23\right)^n +\binom32\left(\frac13\right)^n-\binom33\cdot0 =1-3\left(\frac23\right)^n+3\left(\frac13\right)^n.$$