方針
(1) はまず行列の2乗を直接計算し、 という2次の関係式を得る。この関係を繰り返し使えば、 をすべて と の一次式に落とせるので、最後に係数を集める。(2)は頂点 にいるか、底面の4頂点のいずれかにいるかだけを区別すればよい。 からは次に必ず底面へ移り、底面の頂点からは3本の辺のうち1本だけが に向かうため、 という1本の漸化式に閉じる。定数解を引いて等比数列に直し、初期条件 を代入する。
解答
(1)
まずである。一方だから である。これを順に用いるととなる。したがってである。よって求める行列はである。
(2) 秒後に点 が頂点 にある確率を とする。初期状態より である。
頂点 は底面の4頂点と辺で結ばれているので、 にいる点は次の1秒で必ず 以外へ移る。また、底面の各頂点から出る辺は、頂点 へ向かう1本と、底面上の隣の2頂点へ向かう2本の合計3本である。したがって、 秒後に 以外にいる確率 のうち、次に へ移る確率は であるから を得る。
この漸化式の定数解を とすると より である。よってとなる。したがってである。ゆえに である。
5頂点を「」と「底面」の2状態へまとめると、漸化式が1本に閉じる。
別解
解法2(多項式の剰余と2状態行列)
方針
(1) ではが満たす2次式を法として与式の多項式を1次式へ還元する。(2)ではと底面の2状態の遷移行列を作り、一定の成分と毎回倍される差の成分に分ける。
解答
(1) である。したがって多項式をで割った余りだけを求めればよい。関係を順に用いるとよってしたがって(2)
秒後ににいる確率と底面にいる確率を並べた列ベクトルをとする。遷移は変化しない成分はである。また、直接掛ければである。そこで初期ベクトルをと分ければ第1成分からを得る。
総評
難度4、計算量4。(1)は高次の行列を掛け続けず、で次数を落とす。(2)は5頂点をと底面の2状態へまとめるのが本質である。確率漸化式と2状態遷移行列の2解法を収録した。、底面からへ戻る確率がである根拠を明記したい。15分から20分が目安である。