方針
(1) から(3)までは文系第2問と同じく,頂点をからの距離1,距離2,距離3の3状態にまとめ,へ戻らない確率の漸化式を立てる。偶奇で状態が分かれるためから一般項を得る。(4)では,2回目の帰還が時刻で起こる事象を,初帰還時刻と,その後の初帰還時刻に分解する。したがってはの畳み込みになり,を個別に処理したあと,で不等式を比較する。
解答
(1)
頂点から辺の本数で距離1の頂点の群を,距離2の頂点の群を,距離3の頂点の群をと呼ぶ。
時刻1では必ずにいるので である。の各頂点からは,1本がへ,2本がへ向かう。へ戻る場合はには含めないので である。 の各頂点からは2本がへ,1本がへ向かうから である。
(2) へ戻らない道だけを追うと,遷移はである。したがってである。 より,について である。偶数時刻にはにはいないので である。
またであり,である。よってを得る。
(3)
時刻で初めてに戻るには,時刻までに戻らず,その時刻ににいて,次の1歩でへ進めばよい。からへ進む確率はである。
したがって であり,では である。
(4)
時刻でに戻るのがちょうど2回目であるためには,ある について,時刻に初めてに戻り,そこからさらに後に初めてに戻ればよい。に戻った後は同じ条件で再出発するので である。
まず であり, だからである。また であり, だからである。
次にとする。と,で を用いると,端の2項と中央の項に分けて である。よってとなり,整理して である。一方である。したがっては すなわち と同値である。これは を意味するので,では成り立たない。
以上より,求めるは である。
別解
解法2
方針
2歩を1ブロックとして非帰還経路を直接数える。距離2の群 から2歩後にも にいる非帰還経路は9通り中7通りなので、確率漸化式を解かず一般項が得られる。(4)は最初の帰還時刻で事象を分割し、初帰還確率の積を足す。端の と等比型の中央項を分ける。
解答
頂点を からの距離でまとめ、距離1、2、3の頂点群を とする。
(1)
最初の1歩で必ず に入る。 からは3本中2本が 、1本が へ向かうからさらに からは3本中2本が 、1本が へ向かうので(2)
から2歩進み、途中で を通らず再び に入る経路はの 通りと、の 通り、計7通りである。よって偶数時刻には にいない。また からの次の1歩を数えると(3)
初帰還の直前には におり、最後に確率 で へ進む。したがって(4)
最初の帰還が時刻 、そこから次の初帰還までが である事象へ分けるとまずまた では両端と中央の項を分けて一方したがって はと同値で、 では成立しない。よってである。
総評
難度7,計算量6。目安時間は28分。(1)から(3)は文系版と同じ3状態整理で処理できるが,理系版では(4)の「ちょうど2回目」を初帰還確率の積に分解できるかが山場である。を単なる帰還確率として数えると,途中で複数回戻る場合を混ぜてしまう。だけ式が別になるため,を先に処理し,で端の項と中央の項を分けると計算が整理しやすい。