トップ› 東京工業大学› 2017年› 理系第4問

東京工業大学 2017年理系第4問解説

方針・初手

(1) では、長さ $n$ の文字列のうち条件 $(*)$ を満たすものの個数を漸化式を用いて求める。その際、末尾の文字が $\text{a}$ または $\text{b}$ であるか、$\text{c}$ であるかで次に付け加えられる文字の条件が変わるため、この2つの状態に分けて連立漸化式を立てるのが定石である。 (2) は条件付き確率の定義に従う。指定された位置の文字が固定されているため、文字列をその文字の前後で分割し、それぞれの場合の数の積として事象の要素数を計算して極限をとる。

解法1

(1)

集合 $A_n$ の要素の総数は $3^n$ 個であり、これらはすべて等確率で選ばれる。長さ $n$ の文字列のうち、条件 $(*)$ を満たすものの個数を $a_n$ とする。そのうち、末尾が $\text{a}$ または $\text{b}$ であるものの個数を $x_n$、末尾が $\text{c}$ であるものの個数を $y_n$ とすると、$a_n = x_n + y_n \ (n \geqq 1)$ が成り立つ。

$n=1$ のとき、文字 $\text{a, b, c}$ はいずれも $(*)$ を満たすため、 $x_1 = 2, \ y_1 = 1, \ a_1 = 3$

$n \geqq 1$ において、長さ $n+1$ の $(*)$ を満たす文字列について考える。末尾が $\text{a}$ または $\text{b}$ となるのは、長さ $n$ の $(*)$ を満たす任意の文字列の末尾に $\text{a}$ または $\text{b}$ を付け加えた場合であるから、 $x_{n+1} = 2(x_n + y_n) = 2a_n$

末尾が $\text{c}$ となるのは、末尾が $\text{c}$ でない長さ $n$ の $(*)$ を満たす文字列の末尾に $\text{c}$ を付け加えた場合であるから、 $y_{n+1} = x_n$

これらより、$a_{n+1}$ は次のように表される。

$$ \begin{aligned} a_{n+1} &= x_{n+1} + y_{n+1} \\ &= 2a_n + x_n \end{aligned} $$

ここで、$n \geqq 2$ のとき $x_n = 2a_{n-1}$ であるから、これを代入して次の漸化式を得る。

$$ a_{n+1} = 2a_n + 2a_{n-1} \quad (n \geqq 2) $$

また、$a_2 = x_2 + y_2 = 2a_1 + x_1 = 2 \cdot 3 + 2 = 8$ である。特性方程式 $\lambda^2 - 2\lambda - 2 = 0$ の解は $\lambda = 1 \pm \sqrt{3}$ である。 $\alpha = 1+\sqrt{3}, \ \beta = 1-\sqrt{3}$ とおくと、漸化式は次のように変形できる。

$$ \begin{cases} a_{n+1} - \alpha a_n = \beta (a_n - \alpha a_{n-1}) \\ a_{n+1} - \beta a_n = \alpha (a_n - \beta a_{n-1}) \end{cases} $$

数列 $\{a_{n+1} - \alpha a_n\}$ は、初項 $a_2 - \alpha a_1 = 8 - 3(1+\sqrt{3}) = 5 - 3\sqrt{3}$、公比 $\beta$ の等比数列である。ここで、$(2-\sqrt{3})\beta = (2-\sqrt{3})(1-\sqrt{3}) = 5 - 3\sqrt{3}$ であるから、

$$ a_{n+1} - \alpha a_n = (2-\sqrt{3}) \beta^n $$

同様に、数列 $\{a_{n+1} - \beta a_n\}$ は、初項 $a_2 - \beta a_1 = 8 - 3(1-\sqrt{3}) = 5 + 3\sqrt{3}$、公比 $\alpha$ の等比数列であり、$(2+\sqrt{3})\alpha = 5 + 3\sqrt{3}$ より、

$$ a_{n+1} - \beta a_n = (2+\sqrt{3}) \alpha^n $$

この2式の辺々を引いて整理すると、

$$ (\alpha - \beta) a_n = (2+\sqrt{3}) \alpha^n - (2-\sqrt{3}) \beta^n $$

$\alpha - \beta = 2\sqrt{3}$ であるから、$a_n$ は次のように求まる。

$$ a_n = \frac{(2+\sqrt{3})(1+\sqrt{3})^n - (2-\sqrt{3})(1-\sqrt{3})^n}{2\sqrt{3}} $$

求める確率 $P(n)$ は $\frac{a_n}{3^n}$ であるから、

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

(2)

$A_n$ から選んだ要素が条件 $(*)$ を満たし、その7番目の文字が $\text{c}$ である事象を $X$ とする。また、選んだ要素が条件 $(*)$ を満たし、7番目と10番目の文字がともに $\text{c}$ である事象を $Y$ とする。求める条件付き確率 $Q(n)$ は、$Q(n) = \frac{n(Y)}{n(X)}$ である（$n(X), n(Y)$ はそれぞれ事象 $X, Y$ に属する要素の個数）。

文字列を $c_1 c_2 \dots c_n$ と表す。事象 $X$ が起こるための条件は、文字列が以下の2つの部分に分割でき、全体として $(*)$ を満たすことである。

（i）前半 $c_1 \dots c_7$ ($c_7 = \text{c}$) 長さ 7 で $(*)$ を満たし、末尾が $\text{c}$ の文字列であるから、その個数は $y_7$ 通りである。

（ii）後半 $c_8 \dots c_n$ $c_7 = \text{c}$ であるため $(*)$ を満たすには $c_8 \neq \text{c}$、すなわち先頭が $\text{a}$ または $\text{b}$ でなければならない。長さ $n-7$ で $(*)$ を満たし、先頭が $\text{a}$ または $\text{b}$ である文字列の個数は、対称性から末尾が $\text{a}$ または $\text{b}$ であるものの個数と等しく、$x_{n-7}$ 通りである。

これらは独立に選べるため、$n(X) = y_7 \cdot x_{n-7}$ 通りとなる。 $k \geqq 2$ において $y_k = x_{k-1} = 2a_{k-2}$ であるから、$y_7 = 2a_5$、$x_{n-7} = 2a_{n-8}$。

$$ n(X) = 2a_5 \cdot 2a_{n-8} = 4a_5 a_{n-8} $$

次に事象 $Y$ が起こるための条件は、文字列が以下の3つの部分に分割でき、全体として $(*)$ を満たすことである。前提として $c_7 = \text{c}$ かつ $c_{10} = \text{c}$ である。

（ア）前半 $c_1 \dots c_7$ 事象 $X$ と同様に $y_7 = 2a_5$ 通り。

（イ）中間 $c_8 c_9$ $c_7 = \text{c}$ かつ $c_{10} = \text{c}$ より、$c_8 \in \{\text{a}, \text{b}\}$ かつ $c_9 \in \{\text{a}, \text{b}\}$ である。このとき文字列は $(*)$ を満たす。選び方は $2 \times 2 = 4$ 通り。

（ウ）後半 $c_{11} \dots c_n$ $c_{10} = \text{c}$ より先頭は $c_{11} \in \{\text{a}, \text{b}\}$ となる。長さ $n-10$ で先頭が $\text{a}$ または $\text{b}$ である $(*)$ を満たす文字列の個数であるから、$x_{n-10} = 2a_{n-11}$ 通り。

これらも独立に選べるため、

$$ n(Y) = 2a_5 \cdot 4 \cdot 2a_{n-11} = 16a_5 a_{n-11} $$

したがって、$Q(n)$ は次のように表される。

$$ Q(n) = \frac{16a_5 a_{n-11}}{4a_5 a_{n-8}} = \frac{4a_{n-11}}{a_{n-8}} $$

$a_n = \frac{C \alpha^n - D \beta^n}{2\sqrt{3}}$ ($C=2+\sqrt{3}, D=2-\sqrt{3}$) とおいて極限を計算する。

$$ Q(n) = \frac{4 (C \alpha^{n-11} - D \beta^{n-11})}{C \alpha^{n-8} - D \beta^{n-8}} = \frac{4 \alpha^{-11} - \frac{4D}{C} \beta^{-11} \left(\frac{\beta}{\alpha}\right)^n}{\alpha^{-8} - \frac{D}{C} \beta^{-8} \left(\frac{\beta}{\alpha}\right)^n} $$

$|\beta| < |\alpha|$ より $\lim_{n \to \infty} \left(\frac{\beta}{\alpha}\right)^n = 0$ であるから、

$$ \lim_{n \to \infty} Q(n) = \frac{4 \alpha^{-11}}{\alpha^{-8}} = 4 \alpha^{-3} = \frac{4}{(1+\sqrt{3})^3} $$

これを計算すると、

$$ \frac{4}{1+3\sqrt{3}+9+3\sqrt{3}} = \frac{4}{10+6\sqrt{3}} = \frac{2}{5+3\sqrt{3}} $$

分母を有理化して、

$$ \frac{2(5-3\sqrt{3})}{25-27} = 3\sqrt{3} - 5 $$

解説

本問は、特定の禁止文字列（本問では「$\text{c}$ が連続する」）を含まない文字列の個数を数え上げる、典型的な漸化式の問題である。 (1) では、末尾の文字によって次に付け加えられる文字の制限が変わることに着目し、状態を2つ（末尾が $\text{a}, \text{b}$ か、末尾が $\text{c}$ か）に分けて連立漸化式を立てるのが定石である。 (2) では、固定された文字（$c_7$ や $c_{10}$）を境にして文字列を独立したブロックに分割し、それぞれの場合の数を積の法則で求める発想が求められる。後半の計算においては、特性方程式の解 $\alpha, \beta$ を用いた $a_n$ の一般項の極限の扱いに慣れているかどうかが鍵となる。