1東京医科歯科大学 2011年 数学 第1問解答・解説

$a_m$ を、3回連続の表を含まない長さ $m$ の表裏列の数とする。操作が $n$ 回以上続くのは最初の $n-1$ 回に表3連続がないときなので $$\displaystyle Q_n=\frac{a_{n-1}}{2^{n-1}}.$$ 安全な列を末尾が裏、裏表、裏表表の3通りに分けると（短い場合の初期値も含め） $$a_0=1,\quad a_1=2,\quad a_2=4,\quad a_m=a_{m-1}+a_{m-2}+a_{m-3}\ (m\ge3).$$ よって $a_3=7,\ a_4=13,\ a_5=24,\ a_6=44$ である。

(1) $P_3=1/2^3=1/8$。$n\ge4$ でちょうど $n$ 回目に終了するには、最後の3回が表で、その直前の第 $n-3$ 回が裏でなければならない。それより前の $n-4$ 回には表3連続がない。したがって $$\displaystyle P_n=\frac{a_{n-4}}{2^n}\quad(n\ge4).$$ これより $$\displaystyle P_4=\frac1{16},\quad P_5=\frac2{32}=\frac1{16},\quad P_6=\frac4{64}=\frac1{16},\quad P_7=\frac7{128}.$$

(2) 上の $a_m$ の値から $$\displaystyle Q_6=\frac{a_5}{2^5}=\frac{24}{32}=\frac34,\qquad Q_7=\frac{a_6}{2^6}=\frac{44}{64}=\frac{11}{16}.$$

(3) $Q_{n-1}-Q_n=P_{n-1}$ である。$n-1$ 回目に初めて終了するには、最初の $n-5$ 回に表3連続がなく、第 $n-4$ 回が裏、その後の3回が表となる。独立性より $$\displaystyle P_{n-1}=Q_{n-4}\cdot\frac12\cdot\left(\frac12\right)^3 =\frac1{16}Q_{n-4}.$$ ゆえに $$\displaystyle Q_n-Q_{n-1}=-\frac1{16}Q_{n-4}\quad(n\ge5).$$

(4) 初期値は $$\displaystyle Q_4=\frac78,\quad Q_5=\frac{13}{16},\quad Q_6=\frac34,\quad Q_7=\frac{11}{16}.$$ これらはそれぞれ $$\displaystyle \left(\frac78\right)^4=\frac{2401}{4096}<\frac34,\quad \left(\frac{13}{16}\right)^2=\frac{169}{256}<\frac34,\quad \left(\frac34\right)^4<\left(\frac34\right)^3,\quad \frac{11}{16}<\frac34$$ より、$Q_n<(3/4)^{(n-3)/4}$ を $n=4,5,6,7$ で満たす。

$n\ge8$ とする。(3)を $k=n-3,n-2,n-1,n$ に適用して足すと $$\displaystyle Q_n=Q_{n-4}-\frac1{16}\left(Q_{n-7}+Q_{n-6}+Q_{n-5}+Q_{n-4}\right).$$ $Q_j$ は $j$ とともに非増加なので、括弧内の各項は $Q_{n-4}$ 以上である。したがって $$\displaystyle Q_n\le\frac34Q_{n-4}.$$ 帰納法の仮定 $Q_{n-4}<(3/4)^{(n-7)/4}$ を用いれば $$\displaystyle Q_n\le\frac34Q_{n-4} <\left(\frac34\right)^{1+(n-7)/4} =\left(\frac34\right)^{(n-3)/4}.$$ 以上によりすべての $n\ge4$ で示された。