京都大学 2008年度 前期日程 第2次学力試験理系（甲）数学 第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$ である。

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

全 $3^n$ 経路を、時刻 $n$ までに訪れた頂点が2個・3個・4個のものへ分ける。ちょうど2頂点を訪れた経路数は常に3。ちょうど3頂点を訪れた経路数の漸化式を解き、全経路数から引く。

$n\geqq 1$ とする。時刻 $n$ までに訪れた頂点がちょうど2個、3個、4個である経路数を、それぞれ $b_n,c_n,d_n$ とする。

ちょうど2頂点だけを訪れるには、$A$ と $B,C,D$ のいずれか1頂点との間を交互に動くしかない。相手の選び方が3通りあるので$$b_n=3$$である。

ちょうど3頂点を訪れた経路が次の1秒後にも3頂点だけを訪れるには、現在位置以外の訪問済み2頂点のどちらかへ動けばよいので2通りである。また、ちょうど2頂点を訪れた経路から新しい1頂点へ動く方法も2通りである。したがって$$c_{n+1}=2c_n+2b_n=2c_n+6,c_1=0.$$これを解くと$$c_n=3\cdot 2^n-6$$となる。

時刻 $n$ までの全経路数は $3^n$ 通りであり、$n\geqq 1$ では訪問頂点数は2、3、4のいずれかである。よって$$\begin{array}{rl}{\displaystyle d_n}& {\displaystyle =3^n-b_n-c_n}\\ {\displaystyle }& {\displaystyle =3^n-3-(3\cdot 2^n-6)}\\ {\displaystyle }& {\displaystyle =3^n-3\cdot 2^n+3.}\end{array}$$したがって求める確率は$${\displaystyle \frac{d_n}{3^n}}={\displaystyle \frac{3^n-3\cdot 2^n+3}{3^n}}$$である。

矢印上の数は、次の頂点の選び方の数。