解説

方針・初手

石の位置を $X_n$ とし、$n$ 回の試行後の位置分布をまず漸化的に求める。

また、石は隣の点にしか移動しないので、点 $1$ から始めたとき、印のついた点は常に

$$ 1,2,\ldots,\max_{0\leq i\leq n}X_i

$$

の形になる。したがって、印の個数は石がこれまでに到達した最大の点番号で決まる。

解法1

$p_n(k)=P(X_n=k)$ とおく。初期状態は

$$ p_0=(1,0,0,0,0)

$$

である。

遷移規則より、

$$ \begin{aligned} p_{n+1}(1)&=\frac{1}{2}p_n(2),\\ p_{n+1}(2)&=p_n(1)+\frac{1}{2}p_n(3),\\ p_{n+1}(3)&=\frac{1}{2}p_n(2)+\frac{1}{2}p_n(4),\\ p_{n+1}(4)&=\frac{1}{2}p_n(3)+p_n(5),\\ p_{n+1}(5)&=\frac{1}{2}p_n(4) \end{aligned}

$$

である。これを順に計算すると、

$$ \begin{aligned} p_1&=(0,1,0,0,0),\\ p_2&=\left(\frac12,0,\frac12,0,0\right),\\ p_3&=\left(0,\frac34,0,\frac14,0\right),\\ p_4&=\left(\frac38,0,\frac12,0,\frac18\right),\\ p_5&=\left(0,\frac58,0,\frac38,0\right),\\ p_6&=\left(\frac{5}{16},0,\frac12,0,\frac{3}{16}\right) \end{aligned}

$$

となる。

したがって、6回後に石が点 $1,2,3,4,5$ にある確率はそれぞれ

$$ \frac{5}{16},\ 0,\ \frac12,\ 0,\ \frac{3}{16}

$$

である。

次に、6回後までに5つの点すべてに印がついている確率を求める。

5つの点すべてに印がつくためには、石が点 $5$ に到達すればよい。点 $1$ から点 $5$ に到達するには少なくとも4回の移動が必要であり、6回以内では点 $5$ に初めて到達する時刻は4回目または6回目である。

（i） 4回目に初めて点 $5$ に到達する場合

このとき経路は

$$ 1\to 2\to 3\to 4\to 5

$$

に限られる。その確率は

$$ 1\cdot \frac12\cdot \frac12\cdot \frac12=\frac18

$$

である。残り2回の移動はどのように動いても、すでに全点に印がついている。

（ii） 6回目に初めて点 $5$ に到達する場合

この場合の経路は次の3通りである。

$$ \begin{aligned} &1\to2\to1\to2\to3\to4\to5,\\ &1\to2\to3\to2\to3\to4\to5,\\ &1\to2\to3\to4\to3\to4\to5 \end{aligned}

$$

それぞれの確率は

$$ \frac{1}{16},\quad \frac{1}{32},\quad \frac{1}{32}

$$

であるから、合計は

$$ \frac{1}{16}+\frac{1}{32}+\frac{1}{32}=\frac18

$$

である。

よって、6回後までに5つの点すべてに印がついている確率は

$$ \frac18+\frac18=\frac14

$$

である。

最後に、$n$ 回後にちょうど3つの点に印がついている確率を求める。

石は点 $1$ から出発し、隣り合う点にしか移動しないので、ちょうど3つの点に印がついていることは

$$ \max_{0\leq i\leq n}X_i=3

$$

と同値である。

ここで、

$$ A_n=P\left(\max_{0\leq i\leq n}X_i\leq 3\right)

$$

$$ B_n=P\left(\max_{0\leq i\leq n}X_i\leq 2\right)

$$

とおくと、求める確率は

$$ A_n-B_n

$$

である。

まず $B_n$ を求める。最大値が $2$ 以下であるためには、点 $2$ に来るたびに点 $1$ へ戻らなければならない。したがって経路は

$$ 1\to2\to1\to2\to1\to\cdots

$$

に限られる。

点 $2$ から点 $1$ へ戻る選択は $\lfloor n/2\rfloor$ 回必要であり、それぞれ確率 $\frac12$ で起こるので、

$$ B_n=\left(\frac12\right)^{\lfloor n/2\rfloor}

$$

である。

次に $A_n$ を求める。最大値が $3$ 以下であるとは、点 $4$ に到達しないことである。

1回目の移動で必ず点 $2$ に来る。点 $2$ から2回移動して再び点 $2$ に戻り、かつ点 $4$ に行かない動きは

$$ 2\to1\to2

$$

または

$$ 2\to3\to2

$$

である。それぞれの確率は

$$ \frac12\cdot1=\frac12

$$

および

$$ \frac12\cdot\frac12=\frac14

$$

であるから、2回分の移動で点 $4$ に到達せずに点 $2$ に戻る確率は

$$ \frac12+\frac14=\frac34

$$

である。

1回目の移動後、完全な2回移動のまとまりは $\left\lfloor\frac{n-1}{2}\right\rfloor$ 個ある。最後に1回だけ余る場合は、点 $2$ から点 $1$ または点 $3$ に移るだけなので、点 $4$ には到達しない。

したがって、

$$ A_n=\left(\frac34\right)^{\left\lfloor\frac{n-1}{2}\right\rfloor}

$$

である。

よって、ちょうど3つの点に印がついている確率は

$$ \begin{aligned} \left(\frac34\right)^{\left\lfloor\frac{n-1}{2}\right\rfloor} &= \left(\frac12\right)^{\lfloor n/2\rfloor} \end{aligned} $$

である。

解説

この問題では、石の位置そのものだけでなく、「これまでにどこまで到達したか」を見ることが重要である。

点 $1$ から始めて隣の点にしか移動しないため、点 $k$ に到達した時点で点 $1,2,\ldots,k$ にはすべて印がついている。したがって、印の個数は「最大到達点」で決まる。

(3)では「ちょうど3つ」と直接数えるよりも、

$$ \max X_i\leq 3

$$

から

$$ \max X_i\leq 2

$$

を引く方が処理しやすい。これは確率問題でよく使う「ちょうど」を「以下の差」で表す典型的な考え方である。

答え

**(1)**

$$ \left(\frac{5}{16},\ 0,\ \frac12,\ 0,\ \frac{3}{16}\right)

$$

すなわち、点 $1,2,3,4,5$ にある確率はそれぞれ

$$ \frac{5}{16},\ 0,\ \frac12,\ 0,\ \frac{3}{16}

$$

である。

**(2)**

$$ \frac14

$$

**(3)**

$$ \begin{aligned} \left(\frac34\right)^{\left\lfloor\frac{n-1}{2}\right\rfloor} &= \left(\frac12\right)^{\lfloor n/2\rfloor} \end{aligned} $$