東京工業大学 2017年度理系数学第4問解答・解説

問題

$n$ は正の整数とし，文字 a，b，c を重複を許して $n$ 個並べてできる文字列すべての集合を $A_{n}$ とする。 $A_{n}$ の要素に対し次の条件 (＊) を考える。

(＊) 文字 c が2つ以上連続して現れない。

以下 $A_{n}$ から要素を一つ選ぶとき，どの要素も同じ確率で選ばれるとする。

(1) $A_{n}$ から要素を一つ選ぶとき，それが条件 (＊) を満たす確率 $P (n)$ を求めよ。

(2) $n ≧ 12$ とする。 $A_{n}$ から要素を一つ選んだところ，これは条件 (＊) を満たし，その7番目の文字は c であった。このとき，この要素の10番目の文字が c である確率を $Q (n)$ とする。極限値 $lim_{n \to \infty} Q (n)$ を求めよ。

出典：東京工業大学 2017年度前期理系第4問

方針

条件 (＊) を満たす長さ $n$ の文字列の個数を $B_{n}$ とし，最後の文字が c であるかどうかで漸化式を作る。(2) では，7番目が c と決まると6番目と8番目は a または b に限られるので，左右のブロックに分離して数える。10番目も c である場合は9番目と11番目も a または b に限られるため， $Q (n)$ は $B_{n - 11} / B_{n - 8}$ の比に帰着する。最後に (1) の閉じた式から極限を求める。

解答

(1)

条件 (＊) を満たす長さ $n$ の文字列の個数を $B_{n}$ とする。空文字列を1個と数えて $B_{0} = 1$ ，また $B_{1} = 3$ である。

$n ≧ 2$ とする。最後の文字が a または b のときは，その前の $n - 1$ 文字は条件 (＊) を満たせばよいので $2 B_{n - 1}$ 通りである。最後の文字が c のときは，その直前は a または b でなければならず，最初の $n - 2$ 文字は条件 (＊) を満たせばよいので $2 B_{n - 2}$ 通りである。したがって $B_{n} = 2 B_{n - 1} + 2 B_{n - 2}$ である。

特性方程式 $r^{2} - 2 r - 2 = 0$ の2解を $α = 1 + 3, β = 1 - 3$ とおくと， $B_{n} = \frac{2 + 3}{2 3} α^{n} + \frac{3 - 2}{2 3} β^{n}$ である。全体の文字列は $3^{n}$ 個なので

P (n) = \frac{1}{3 ^{n}} {\frac{2 + 3}{2 3} (1 + 3)^{n} + \frac{3 - 2}{2 3} (1 - 3)^{n}}

である。

(2)

7番目の文字が c であり条件 (＊) を満たすなら，6番目と8番目の文字は a または b である。1番目から5番目までは条件 (＊) を満たす任意の文字列であり，9番目以降も条件 (＊) を満たす任意の文字列である。したがって，条件 (＊) を満たし7番目が c である文字列の個数は $2^{2} B_{5} B_{n - 8}$ である。

さらに10番目の文字も c であるとする。このとき9番目と11番目も a または b である。よって，条件 (＊) を満たし7番目と10番目がともに c である文字列の個数は $2^{4} B_{5} B_{n - 11}$ である。したがって

Q (n) = \frac{2 ^{4} B _{5} B _{n - 11}}{2 ^{2} B _{5} B _{n - 8}} = 4 \frac{B _{n - 11}}{B _{n - 8}}

である。

ここで $∣ β ∣ < α$ だから，

n \to \infty lim \frac{B _{n - 11}}{B _{n - 8}} = \frac{1}{α ^{3}}

である。よって

n \to \infty lim Q (n) = \frac{4}{( 1 + 3 ) ^{3}} = 33 - 5

である。

東京工業大学 2017年度理系数学 第4問

問題

方針

解答

(1)

(2)

東京工業大学 2017年度
理系数学第4問