解説

方針・初手

散歩する日を $W$，散歩しない日を $N$ として，条件を満たす予定表を長さ $n$ の文字列とみなす。

すると，$f_n$ は

• 末日が必ず $W$
• $NN$ が現れない

ような長さ $n$ の列の総数である。

まず $f_n$ の漸化式を立てる。次に，4日目が散歩しない日である予定表の個数を数えて，全体から引けば $p_n$ が求まる。

解法1

$n$ 日目の1つ前に注目する。

**(i)**

$(n-1)$ 日目が $W$ のとき，最初の $n-1$ 日はそのまま条件を満たす予定表であるから，個数は $f_{n-1}$ 通りである。

**(ii)**

$(n-1)$ 日目が $N$ のとき，$NN$ を避けるため $(n-2)$ 日目は $W$ でなければならない。したがって最初の $n-2$ 日が条件を満たす予定表になればよいので，個数は $f_{n-2}$ 通りである。

よって，

$$ f_n=f_{n-1}+f_{n-2} $$

が成り立つ。

初期値は問題文より

$$ f_1=1,\quad f_2=2,\quad f_3=3 $$

であるから，

$$ f_4=5,\ f_5=8,\ f_6=13,\ f_7=21,\ f_8=34,\ f_9=55,\ f_{10}=89,\ f_{11}=144,\ f_{12}=233 $$

となる。

次に，4日目が散歩しない日である予定表の個数を数える。

4日目が $N$ なら，3日目と5日目は必ず $W$ である。したがって，予定表は

$$ (\text{1日目から3日目});W N W;(\text{6日目から}n\text{日目}) $$

という形になる。

まず，1日目から3日目までの部分は，3日目が $W$ で条件を満たす予定表そのものであるから，その個数は

$$ f_3=3 $$

通りである。

次に，5日目から $n$ 日目までを見る。5日目は $W$ に固定されているので，この先頭の $W$ を取り除くと，6日目から $n$ 日目までの長さ $n-5$ の予定表で，末日が $W$，かつ $NN$ を含まないものがちょうど得られる。逆に，そのような長さ $n-5$ の予定表の先頭に $W$ を付ければ，5日目から $n$ 日目までの部分が復元できる。

よって，5日目から $n$ 日目までの部分の個数は

$$ f_{n-5} $$

通りである。

以上より，4日目が $N$ である予定表の個数は

$$ 3f_{n-5} $$

通りである。したがって，$n\geqq 5$ に対して

$$ p_n=\frac{f_n-3f_{n-5}}{f_n} =1-\frac{3f_{n-5}}{f_n} $$

である。

（1） $p_{12}$

$$ p_{12}=1-\frac{3f_7}{f_{12}} =1-\frac{3\cdot 21}{233} =1-\frac{63}{233} =\frac{170}{233} $$

（2） $\displaystyle \lim_{n\to\infty} p_n$

問題文の結果

$$ \lim_{n\to\infty}\frac{f_{n+1}}{f_n}=\frac{1+\sqrt5}{2} $$

を

$$ \varphi=\frac{1+\sqrt5}{2} $$

とおく。

すると，

$$ \begin{aligned} \frac{f_{n-5}}{f_n} &= \frac{1}{ \left(\dfrac{f_n}{f_{n-1}}\right) \left(\dfrac{f_{n-1}}{f_{n-2}}\right) \left(\dfrac{f_{n-2}}{f_{n-3}}\right) \left(\dfrac{f_{n-3}}{f_{n-4}}\right) \left(\dfrac{f_{n-4}}{f_{n-5}}\right) } \to \frac{1}{\varphi^5} \end{aligned} $$

であるから，

$$ \begin{aligned} \lim_{n\to\infty}p_n &= 1-\frac{3}{\varphi^5} \end{aligned} $$

となる。

ここで，

$$ \varphi^2=\varphi+1 $$

より，

$$ \varphi^3=2\varphi+1,\quad \varphi^4=3\varphi+2,\quad \varphi^5=5\varphi+3 $$

である。したがって，

$$ \begin{aligned} \varphi^5 &= 5\cdot \frac{1+\sqrt5}{2}+3 \\ \frac{11+5\sqrt5}{2} \end{aligned} $$

ゆえに，

$$ \begin{aligned} \lim_{n\to\infty}p_n &= 1-\frac{6}{11+5\sqrt5} \\ \frac{35-15\sqrt5}{2} \end{aligned} $$

となる。

さらに，これが $0.7=\dfrac{7}{10}$ より大きいかを調べると，

$$ \frac{35-15\sqrt5}{2}>\frac{7}{10} $$

は

$$ 175-75\sqrt5>7 $$

すなわち

$$ 168>75\sqrt5 $$

と同値であり，さらに両辺正なので2乗して

$$ 168^2>75^2\cdot 5 $$

を調べればよい。実際，

$$ 28224>28125 $$

であるから，

$$ \frac{35-15\sqrt5}{2}>0.7 $$

が成り立つ。

解説

$f_n$ は末尾に注目するとすぐにフィボナッチ型の漸化式になる。

また，確率を直接求めるよりも，「4日目が散歩しない日である場合」を数えて補集合で処理するのが自然である。4日目が $N$ なら前後が必ず $W$ になるため，予定表が前半と後半にきれいに分解できる。この分解が本問の核心である。

極限では，$p_n=1-\dfrac{3f_{n-5}}{f_n}$ の形まで持ち込めば，与えられた極限 $\displaystyle \frac{f_{n+1}}{f_n}\to \frac{1+\sqrt5}{2}$ をそのまま使える。

答え

**(1)**

$$ p_{12}=\frac{170}{233} $$

**(2)**

$$ \begin{aligned} \lim_{n\to\infty}p_n &= 1-\frac{3}{\left(\frac{1+\sqrt5}{2}\right)^5} \\ \frac{35-15\sqrt5}{2} \end{aligned} $$

したがって，その極限値は $0.7$ より大きい。