解説

方針・初手

2つの粒子が「同じ点にいるか」「異なる点にいるか」だけに注目する。

三角形の各頂点からは、必ず他の2頂点のどちらかへ確率 $\dfrac12$ で移動する。したがって、2つの粒子が同じ頂点にいる場合と異なる頂点にいる場合で、1秒後に同じ頂点にいる確率を計算すればよい。

解法1

時刻 $n$ 秒後に2つの粒子が同じ点にいる確率を $p(n)$ とする。

まず、時刻 $n$ 秒後に2つの粒子が同じ点にいる場合を考える。このとき、2つの粒子は同じ頂点から出発し、それぞれ隣の2頂点のどちらかへ確率 $\dfrac12$ で移動する。

2つの粒子が1秒後も同じ点にいるには、同じ行き先を選べばよい。したがって、その確率は

$$ \left(\frac12\right)^2+\left(\frac12\right)^2=\frac12

$$

である。

次に、時刻 $n$ 秒後に2つの粒子が異なる点にいる場合を考える。例えば、一方が $A$、もう一方が $B$ にいるとする。このとき、$A$ にいる粒子は $B$ または $C$ に移動し、$B$ にいる粒子は $A$ または $C$ に移動する。

1秒後に同じ点にいるには、両方とも残りの頂点 $C$ に移動する場合しかない。よって、その確率は

$$ \frac12\cdot \frac12=\frac14

$$

である。

したがって、漸化式

$$ p(n+1)=\frac12p(n)+\frac14{1-p(n)}

$$

を得る。整理すると

$$ p(n+1)=\frac14p(n)+\frac14

$$

である。

ここで定数解を求めると、$p=\dfrac14p+\dfrac14$ より

$$ p=\frac13

$$

である。よって

$$ p(n+1)-\frac13=\frac14\left(p(n)-\frac13\right)

$$

となる。

時刻 $0$ では2つの粒子はともに $A$ にいるので

$$ p(0)=1

$$

である。したがって

$$ \begin{aligned} p(n)-\frac13 &= \left(\frac14\right)^n\left(p(0)-\frac13\right) \end{aligned} $$

より

$$ \begin{aligned} p(n)-\frac13 &= \left(\frac14\right)^n\cdot \frac23 \end{aligned} $$

である。

ゆえに

$$ p(n)=\frac13+\frac23\left(\frac14\right)^n

$$

を得る。

解法2

1つの粒子が時刻 $n$ 秒後に各頂点にいる確率を求め、それを用いて2つの粒子が一致する確率を計算する。

1つの粒子について、時刻 $n$ 秒後に $A$ にいる確率を $a_n$ とする。三角形は対称なので、$B,C$ にいる確率は等しい。よって

$$ P(B)=P(C)=\frac{1-a_n}{2}

$$

である。

次の時刻に $A$ にいるには、直前に $B$ または $C$ にいて、そこから $A$ に移動すればよい。したがって

$$ \begin{aligned} a_{n+1} &= \frac12{P(B)+P(C)} \\ \frac12(1-a_n) \end{aligned} $$

である。

これを整理すると

$$ \begin{aligned} a_{n+1}-\frac13 &= -\frac12\left(a_n-\frac13\right) \end{aligned} $$

となる。初期条件は $a_0=1$ であるから

$$ \begin{aligned} a_n-\frac13 &= \left(-\frac12\right)^n\left(1-\frac13\right) \end{aligned} $$

より

$$ a_n=\frac13+\frac23\left(-\frac12\right)^n

$$

である。

したがって、時刻 $n$ 秒後に1つの粒子が各頂点にいる確率は

$$ P(A)=\frac13+\frac23\left(-\frac12\right)^n

$$

であり、

$$ P(B)=P(C)=\frac13-\frac13\left(-\frac12\right)^n

$$

である。

2つの粒子は独立に動くので、同じ頂点にいる確率は

$$ p(n)=P(A)^2+P(B)^2+P(C)^2

$$

である。よって

$$ \begin{aligned} p(n) &= \left\{\frac13+\frac23\left(-\frac12\right)^n\right\}^2 +2\left\{\frac13-\frac13\left(-\frac12\right)^n\right\}^2 \\ &= \frac13+\frac23\left(\frac14\right)^n \end{aligned}

$$

となる。

解説

この問題では、各粒子の位置を直接追うよりも、2つの粒子の関係が「一致しているか」「一致していないか」に注目するのが最も簡潔である。

一致している状態から次も一致する確率は $\dfrac12$、一致していない状態から次に一致する確率は $\dfrac14$ である。この2つを押さえると、求める確率は1次の漸化式で処理できる。

別解のように1つの粒子の分布を求めてから、独立性を用いて一致確率を計算する方法も自然である。ただし、この方法では各頂点にいる確率を求める手間が増えるため、本問では状態を「同じか異なるか」にまとめる解法の方が効率的である。

答え

$$ p(n)=\frac13+\frac23\left(\frac14\right)^n

$$