方針
立方体の頂点を,頂点から辺何本で到達できるかによって3つの群に分ける。距離1の群を,距離2の群を,対頂点をとすると,へ戻らない条件を保ったまま3状態の漸化式が立つ。偶数時刻ではだけ,奇数時刻ではだけが現れるため,に落として一般項を求める。初帰還確率は,直前に距離1の群にいて次にへ進む確率として表す。
解答
頂点から辺の本数で距離1の頂点の群を,距離2の頂点の群を,距離3の頂点の群をと呼ぶ。問題のは,時刻までに戻っていないという条件を含んだまま,それぞれの群にいる確率である。
(1)
時刻1では必ずのどれかにいるので である。の頂点からは,1本がへ戻る辺,残り2本がへ進む辺である。したがって である。
次に,の頂点からは2本がへ,1本がへ向かう。よって である。
(2) で,へ戻らない道だけを数えると,遷移はである。第2式に第1式と第3式を2時刻分ずらして用いるとを得る。 であるから,について である。また偶数時刻にはにはいないので である。
一方,奇数時刻については および であり,である。したがってである。
(3)
時刻で初めてに戻るには,時刻までに戻らず,時刻に距離1の群にいて,次の1歩でへ進めばよい。の各頂点からへ進む確率はである。 のときは,時刻1で必ずにいるから である。のときは(2)よりである。
別解
解法2
方針
確率漸化式を使わず、 からの距離によって頂点を の3群に分け、2歩単位の非帰還経路を数える。 から2歩後に再び に入る経路は、 の4通りと の3通り、計7通りである。この9通り中7通りのブロックを反復する。
解答
頂点を からの距離でまとめ、距離1、2、3の頂点群をそれぞれ とする。
(1)
最初の1歩では必ず にいる。 からは3本中2本が 、1本が へ向かうのでさらに からは3本中2本が 、1本が へ向かうため(2)
の1頂点から2歩進み、途中で を通らず再び に入る経路を数える。は 通り、は 通りである。よって全 通り中7通りが非帰還条件を保つ。時刻2で にいる確率が なので偶数時刻には にいない。また からの次の1歩を数えると(3)
時刻 に初めて へ戻るには、直前まで帰還せず にいて、最後に確率 で へ進めばよい。したがってまた では
総評
難度6,計算量5。目安時間は20分。8頂点を個別に追うと煩雑だが,からの距離での3状態にまとめると見通しがよい。確率は「まだに戻っていない」ことを含む無条件確率なので,からへ戻る枝は次時刻のには入れない。偶奇で0になる状態を明示し,初帰還では直前のからを掛けるところが採点点である。