方針
行き方の数では、 に入る直前が である場合と、 と進む場合に分ける。戻れない条件により、 の直前は必ず になる。同様に についても漸化式が立つ。出会う確率は時刻 に が にいることから、可能な時刻が だけに絞られる。時刻4は一直線に進む1通り、時刻5は戻れない条件で確率の異なる6通りを列挙して合計する。
解答
(1)
まず行き方の数を調べる。 に到る最後の部分は、次の2種類に分けられる。
1つは と進む場合である。もう1つは と進む場合であるが、直前の点に戻ることはできないので、この直前は ではなく でなければならない。したがってこの場合の最後の部分は である。よって である。同様に である。
初めに にいるので への行き方は1通りである。また へは の1通りで到るから である。したがって である。よって である。
(2)
上の漸化式で、 である。もし なら である。よって数学的帰納法により である。
(3)
点 は時刻 に にいる。ただし とする。点 は1秒で添字を高々1だけ増やすので、 と が出会うには が必要である。また が にいるには、時刻 までの横方向の移動回数が であり、残りの縦方向の移動回数は である。 側に戻っているためには縦移動回数は偶数である。これらを合わせると、実際に出会える時刻は だけである。
時刻4で出会うには と進むしかない。各時刻で2通りの選択があるので、その確率は である。
時刻5で出会うには にいる必要がある。可能な経路とその確率は次の通りである。である。確率が になる経路があるのは、途中で直前の点へ戻れず、次の移動が強制される箇所があるためである。したがって時刻5で出会う確率は である。
時刻4と時刻5の出会いは同時には起こらない。よって求める確率は である。
別解
解法2(状態確率表で出会いを追う)
方針
行き方の数は対称な2変数漸化式を行列で解く。
出会いについては「直前の点」と「現在の点」を状態に含め、
戻れないため選択が1通りになる場合も反映した確率表を時刻5まで作る。
解答
(1)
最後に水平に進む場合と、反対側から縦に移る場合を分けると だから(2)
は上の行列で2倍される。初期ベクトルも なのでしたがって(3)
時刻 の は にいる。添字の増加回数と上下移動の偶奇から、
出会えるのは の と、 の だけである。
戻り禁止を含めて状態確率を順に更新すると、必要な成分はとなる。実際、 へは4回連続で上段を進む1経路だけで確率 。
へは、確率 の3経路と、途中の移動が強制されて確率 となる3経路があり、2事象は排反なので
総評
難度8、計算量7。図の欠落していた梯子状の点配置を復元した。行き方の数と各経路の確率は同じではなく、戻り禁止で移動が強制される状態を区別する必要がある。時刻4と5の排反な出会いを状態表と経路列挙で照合した。 2つの解法は着眼点を分け、必要性・十分性、端点、等号条件を省略せず記述した。