解説

方針・初手

終了するためには、最後の2回が「表・表」であり、それ以前には「表・表」が連続して現れていてはならない。

また、$n\geqq 3$ のとき、最後の2回が表で終了するなら、その直前の $(n-2)$ 回目は裏でなければならない。したがって、終了する列は末尾が「裏・表・表」となることに注目する。

解法1

表を $H$、裏を $T$ と書く。

**(1)**

$P_2,P_3,P_4$ を求める。

2回で終了するのは

$$ HH

$$

の場合だけであるから、

$$ P_2=\frac{1}{2^2}=\frac14

$$

である。

3回で終了するには、最後の2回が $HH$ であり、1回目は $T$ でなければならない。よって

$$ THH

$$

のみであるから、

$$ P_3=\frac{1}{2^3}=\frac18

$$

である。

4回で終了するには、3回目と4回目が $HH$、2回目が $T$ であればよい。1回目は $H,T$ のどちらでもよいので、

$$ HTHH,\quad TTHH

$$

の2通りである。したがって

$$ P_4=\frac{2}{2^4}=\frac18

$$

である。

（2） 漸化式を求める。

$n+1$ 回目で終了する列を考える。最後の2回は $HH$ であり、その直前は $T$ でなければならない。したがって、末尾は

$$ THH

$$

である。

ここで、最初の $n-2$ 回の中には $HH$ が連続して現れてはならない。

そこで、$HH$ を含まない長さ $m$ の列の個数を $a_m$ とする。このとき、長さ $m$ の列は、最後が $T$ のものと最後が $H$ のものに分けられる。

最後が $T$ なら、その前の $m-1$ 個は任意の $HH$ を含まない列でよいので $a_{m-1}$ 通りである。

最後が $H$ なら、その直前は $T$ でなければならないから、末尾は $TH$ である。その前の $m-2$ 個は任意の $HH$ を含まない列でよいので $a_{m-2}$ 通りである。

よって

$$ a_m=a_{m-1}+a_{m-2}

$$

が成り立つ。

$n\geqq 3$ のとき、$n$ 回目で終了する列は、最初の $n-3$ 回が $HH$ を含まない列で、末尾が $THH$ である。したがって

$$ P_n=\frac{a_{n-3}}{2^n}

$$

である。

よって

$$ \begin{aligned} P_{n+1} &=\frac{a_{n-2}}{2^{n+1}} \\ &=\frac{a_{n-3}+a_{n-4}}{2^{n+1}} \\ &=\frac12\cdot \frac{a_{n-3}}{2^n}+\frac14\cdot \frac{a_{n-4}}{2^{n-1}} \\ &=\frac12P_n+\frac14P_{n-1} \end{aligned}

$$

となる。したがって、$n\geqq 3$ に対して

$$ P_{n+1}=\frac12P_n+\frac14P_{n-1}

$$

である。

（3） 不等式を示す。

まず $n=2$ のとき、

$$ P_2=\frac14,\quad P_3=\frac18

$$

より

$$ \frac{P_2}{2}=\frac18\leqq P_3=\frac18\leqq \frac14=P_2

$$

である。

次に、ある $n\geqq 3$ に対して

$$ \frac{P_{n-1}}{2}\leqq P_n

$$

が成り立つと仮定する。

(2)より

$$ P_{n+1}=\frac12P_n+\frac14P_{n-1}

$$

である。$P_{n-1}\geqq 0$ だから、

$$ P_{n+1}\geqq \frac12P_n

$$

である。

また、仮定 $\dfrac{P_{n-1}}{2}\leqq P_n$ より

$$ \frac14P_{n-1}\leqq \frac12P_n

$$

である。したがって

$$ P_{n+1} =\frac12P_n+\frac14P_{n-1} \leqq \frac12P_n+\frac12P_n =P_n

$$

である。

よって

$$ \frac{P_n}{2}\leqq P_{n+1}\leqq P_n

$$

が成り立つ。

$n=2$ で成り立ち、上の議論により順に次の場合へ進めるので、すべての $n\geqq 2$ について

$$ \frac{P_n}{2}\leqq P_{n+1}\leqq P_n

$$

が成り立つ。

解説

この問題では、「ちょうど $n$ 回で終了する」という条件を、最後の並びから捉えることが重要である。

最後の2回は必ず $HH$ であり、それより前に $HH$ が出てはいけない。さらに $n\geqq 3$ では、最後の $HH$ の直前は必ず $T$ である。したがって、終了する列は末尾が $THH$ になる。

漸化式では、$HH$ を含まない列の個数を補助的に考えると整理しやすい。これはフィボナッチ型の数え上げになり、最終的に

$$ P_{n+1}=\frac12P_n+\frac14P_{n-1}

$$

が得られる。

不等式の証明では、この漸化式をそのまま使う。下側の不等式は $P_{n-1}\geqq 0$ から直ちに出る。上側の不等式は、一つ前の下側の不等式を利用するのがポイントである。

答え

**(1)**

$$ P_2=\frac14,\quad P_3=\frac18,\quad P_4=\frac18

$$

**(2)**

$n\geqq 3$ に対して

$$ P_{n+1}=\frac12P_n+\frac14P_{n-1}

$$

**(3)**

$n\geqq 2$ に対して

$$ \frac{P_n}{2}\leqq P_{n+1}\leqq P_n

$$

が成り立つ。