京都大学 2008年度
理系数学 第2問

解答

時刻0で点 $P$ は $A$ にいるので，$A$ はすでに現れている。したがって，時刻1から時刻 $n$ までの間に $B,C,D$ の3頂点がすべて現れる確率を求めればよい。

各秒ごとに，現在いる頂点以外の3頂点のどれかへ移るので，全経路数は $3^n$ 通りである。 $B,C,D$ のうち，少なくとも1つが現れない経路を包除原理で数える。例えば $B$ が一度も現れない経路を考える。このとき点 $P$ は $A,C,D$ の3頂点だけを動く。これらのどの頂点にいても，$B$ を避けて次に動く先は2通りあるので，そのような経路は $2^n$ 通りである。避ける頂点は $B,C,D$ の3通りだから，1つの頂点を避ける条件の和は $3\cdot 2^n$ である。

次に，例えば $B$ と $C$ がどちらも現れない経路を考える。このとき動ける頂点は $A$ と $D$ だけであり，時刻0で $A$ にいるので，その後は $A,D,A,D,\dots$ と交互に動くしかない。したがって経路は1通りである。避ける2頂点の選び方は ${}_3{\mathrm{C}}_2=3$ 通りである。

3つすべて $B,C,D$ を避けることは，1秒後にどこかへ移らなければならないため不可能である。よって，時刻1から $n$ までに $B,C,D$ がすべて現れる経路数は $3^n-3\cdot 2^n+3$ である。

したがって求める確率は $\frac{3^n-3\cdot 2^n+3}{3^n}$ である。$n=1,2$ では分子が0になり，3頂点すべてを訪れるには少なくとも3秒必要であることとも一致する。