解説

方針・初手

現在いる部屋が $A_1$ であるかどうかだけに注目する。部屋 $A_1$ にいる確率を $p_n$ とおくと、次の移動で $A_1$ に入るには、直前に $A_1$ 以外の部屋にいて、そこから $A_1$ を選ぶ必要がある。

解法1

$n$ 回移動した後に部屋 $A_1$ にいる確率を $p_n$ とする。最初は部屋 $A_0$ にいるので、

$$ p_0=0

$$

である。

$n$ 回移動した後に $A_1$ にいる確率は $p_n$ であるから、$A_1$ 以外の部屋にいる確率は $1-p_n$ である。

$A_1$ 以外のどの部屋にいても、次に選べる部屋は現在の部屋以外の $k$ 個であり、その中に $A_1$ はちょうど $1$ 個含まれる。したがって、次に $A_1$ へ移動する確率は $\dfrac{1}{k}$ である。

よって漸化式

$$ p_{n+1}=\frac{1-p_n}{k}

$$

を得る。

これを解く。定数解を $p$ とすると、

$$ p=\frac{1-p}{k}

$$

より、

$$ (k+1)p=1

$$

であるから、

$$ p=\frac{1}{k+1}

$$

である。

そこで、

$$ \begin{aligned} p_{n+1}-\frac{1}{k+1} &= -\frac{1}{k}\left(p_n-\frac{1}{k+1}\right) \end{aligned} $$

となる。したがって数列 $p_n-\dfrac{1}{k+1}$ は公比 $-\dfrac{1}{k}$ の等比数列である。

$p_0=0$ より、

$$ \begin{aligned} p_0-\frac{1}{k+1} &= -\frac{1}{k+1} \end{aligned} $$

であるから、

$$ \begin{aligned} p_n-\frac{1}{k+1} &= -\frac{1}{k+1}\left(-\frac{1}{k}\right)^n \end{aligned} $$

となる。よって、

$$ \begin{aligned} p_n &= \frac{1}{k+1} \\ \frac{1}{k+1}\left(-\frac{1}{k}\right)^n \end{aligned} $$

である。

したがって、

$$ \begin{aligned} p_n &= \frac{1}{k+1}\left\{1-\left(-\frac{1}{k}\right)^n\right\} \end{aligned} $$

を得る。

解法2

部屋 $A_1$ 以外の $k$ 個の部屋は、確率を考えるうえでまとめて扱える。$n$ 回移動した後に $A_1$ にいる確率を $p_n$ とする。

各移動で、現在いる部屋以外の $k$ 個の部屋から等確率で選ぶので、$A_1$ にいない状態からは確率 $\dfrac{1}{k}$ で $A_1$ に移る。一方、$A_1$ にいる状態からは、次は必ず $A_1$ 以外へ移る。

したがって、

$$ \begin{aligned} p_{n+1} &= 0\cdot p_n+\frac{1}{k}(1-p_n) \\ \frac{1-p_n}{k} \end{aligned} $$

である。

ここで、

$$ q_n=(k+1)p_n-1

$$

とおく。漸化式より、

$$ \begin{aligned} q_{n+1} &=(k+1)p_{n+1}-1\\ &=(k+1)\frac{1-p_n}{k}-1\\ &=\frac{k+1}{k}-\frac{k+1}{k}p_n-1\\ &=\frac{1}{k}-\frac{(k+1)p_n}{k}\\ &=-\frac{(k+1)p_n-1}{k}\\ &=-\frac{1}{k}q_n \end{aligned}

$$

となる。

また、

$$ q_0=(k+1)p_0-1=-1

$$

であるから、

$$ q_n=-\left(-\frac{1}{k}\right)^n

$$

である。よって、

$$ \begin{aligned} (k+1)p_n-1 &= -\left(-\frac{1}{k}\right)^n \end{aligned} $$

となり、

$$ \begin{aligned} p_n &= \frac{1}{k+1}\left\{1-\left(-\frac{1}{k}\right)^n\right\} \end{aligned} $$

を得る。

解説

この問題では、$k+1$ 個の部屋すべての確率を個別に追う必要はない。求めたいのは $A_1$ にいる確率だけなので、「$A_1$ にいるか、いないか」の2状態に縮約するのが最短である。

注意すべき点は、$A_1$ にいるときは次に $A_1$ に残れないことである。したがって、$p_{n+1}$ は $p_n$ からではなく、$1-p_n$ から作る必要がある。

また、$k=1$ の場合も式は成り立つ。このとき部屋は $A_0,A_1$ の2つだけで、移動のたびに交互に部屋を移る。公式は

$$ p_n=\frac{1}{2}{1-(-1)^n}

$$

となり、$n$ が奇数なら $1$、偶数なら $0$ で、実際の動きと一致する。

答え

$n$ 回移動した後に部屋 $A_1$ にいる確率は、

$$ \boxed{\frac{1}{k+1}\left\{1-\left(-\frac{1}{k}\right)^n\right\}}

$$

である。