東京大学 1992年 文系 第3問 解説

方針・初手

(1) は、数列 $X_n$ に含まれる '$0$' の個数と '$1$' の個数に注目し、連立漸化式を立てることで桁数 $a_n$ の規則性を探る。 (2) は、置き換えの規則によって '$01$' という配列がどのような条件で新たに生成されるかに着目する。文字列が結合される際の境界部分を考えるアプローチと、どの文字から '$01$' が派生したかを追跡するアプローチが有効である。

解法1

(1)

$X_n$ に含まれる '$0$' の個数を $z_n$、'$1$' の個数を $o_n$ とする。 $X_n$ の桁数 $a_n$ は、これらを用いて $a_n = z_n + o_n$ と表される。

問題の規則より、各桁の数字は '$0$' ならば '$1$' に、'$1$' ならば '$10$' に置き換えられる。 どちらの数字も、置き換え後に必ず1つの '$1$' を生み出す。したがって、$X_{n+1}$ に含まれる '$1$' の個数は、$X_n$ のすべての文字の個数（すなわち桁数 $a_n$）に等しい。

$$ o_{n+1} = a_n \quad (n \geqq 1) $$

また、$X_{n+1}$ に含まれる '$0$' は、$X_n$ に含まれる '$1$' が '$10$' に置き換わるときにのみ1つ生成される。したがって、$X_{n+1}$ に含まれる '$0$' の個数は、$X_n$ に含まれる '$1$' の個数に等しい。

$$ z_{n+1} = o_n \quad (n \geqq 1) $$

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

$$ a_{n+1} = z_{n+1} + o_{n+1} = o_n + a_n $$

さらに、$n \geqq 2$ のとき $o_n = a_{n-1}$ であるから、これを代入すると、

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

となる。これはフィボナッチ数列 $\{p_n\}$ の漸化式と同じ形である。

初期値を調べると、 $X_1 = 1$ より $a_1 = 1$ $X_2 = 10$ より $a_2 = 2$ である。一方、与えられた数列 $\{p_n\}$ は $p_1 = 1, p_2 = 1$ であり、$p_{n+2} = p_{n+1} + p_n$ を満たすので、$p_3 = 2$ となる。 したがって $a_1 = p_2$, $a_2 = p_3$ であり、漸化式が一致することから、すべての自然数 $n$ について

$$ a_n = p_{n+1} $$

が成り立つ。 与えられた $p_n$ の一般項に $n+1$ を代入して、

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

(2)

文字列 $A$ と $B$ をこの順に結合してできる文字列を $AB$ と表す。 問題の置き換え規則を文字列に対する操作 $f$ とすると、$f(0)=1, f(1)=10$ であり、任意の文字列 $A, B$ に対して $f(AB) = f(A)f(B)$ が成り立つ。 これを用いて、$X_{n+2} = X_{n+1} X_n$ がすべての自然数 $n$ で成り立つことを数学的帰納法で示す。

(i)

$n=1$ のとき $X_1 = 1, X_2 = 10$ であり、$f(X_2) = 101 = X_3$ となる一方、$X_2 X_1 = 101$ であるから $X_3 = X_2 X_1$ が成り立つ。

(ii)

$n=k$ のとき $X_{k+2} = X_{k+1} X_k$ が成り立つと仮定する。 $n=k+1$ のとき、

$$ X_{k+3} = f(X_{k+2}) = f(X_{k+1} X_k) = f(X_{k+1})f(X_k) = X_{k+2} X_{k+1} $$

となり、成り立つ。 よって、すべての $n \geqq 1$ について $X_{n+2} = X_{n+1} X_n$ が成り立つ。

$X_n$ の中に '$01$' が現れる回数を $b_n$ とする。 $X_{n+2}$ は $X_{n+1}$ の直後に $X_n$ を結合した文字列であるから、$b_{n+2}$ はそれぞれの内部に現れる '$01$' の回数の和に、結合部分で新たに '$01$' が生じる回数 $c_n$ を加えたものになる。

$$ b_{n+2} = b_{n+1} + b_n + c_n $$

結合部分で '$01$' が生じるのは、$X_{n+1}$ の末尾の数字が '$0$' かつ $X_n$ の先頭の数字が '$1$' のときに限られる。 ここで、$X_1 = 1$ であり、置き換え後の文字列は必ず '$1$' から始まるため、すべての $n \geqq 1$ において $X_n$ の先頭の数字は '$1$' である。 次に $X_n$ の末尾の数字 $l_n$ を考える。 $X_{n+2} = X_{n+1} X_n$ であるから、文字列 $X_{n+2}$ の末尾は $X_n$ の末尾に等しく、$l_{n+2} = l_n$ が成り立つ。 $X_1 = 1$ より $l_1 = 1$, $X_2 = 10$ より $l_2 = 0$ であるから、 $n$ が奇数のとき $l_n = 1$ (末尾は '$1$') $n$ が偶数のとき $l_n = 0$ (末尾は '$0$') となる。 したがって、結合部で '$01$' が生じる回数 $c_n$ は、$X_{n+1}$ の末尾が '$0$' となる場合、すなわち $n+1$ が偶数（$n$ が奇数）のときに $1$、そうでないときに $0$ となる。 これを式で表すと $c_n = \frac{1 - (-1)^n}{2}$ となる。ゆえに、

$$ b_{n+2} = b_{n+1} + b_n + \frac{1 - (-1)^n}{2} \quad (n \geqq 1) $$

が成り立つ。

この漸化式から $b_n$ を求める。$b_1=0, b_2=0$ より $b_3=1, b_4=1, b_5=3$ となり、数列 $\{p_n\}$ と比較すると、

$$ b_n = p_{n-1} - \frac{1 + (-1)^n}{2} \quad (n \geqq 2) $$

と推測できる。これを数学的帰納法で示す。

(i)

$n=2, 3$ のとき $b_2 = p_1 - \frac{1 + 1}{2} = 1 - 1 = 0$ $b_3 = p_2 - \frac{1 - 1}{2} = 1 - 0 = 1$ となり成り立つ。

(ii)

$n=k, k+1$ ($k \geqq 2$) のとき成り立つと仮定すると、

$$ b_{k+2} = b_{k+1} + b_k + \frac{1 - (-1)^k}{2} $$

$$ = \left( p_k - \frac{1 + (-1)^{k+1}}{2} \right) + \left( p_{k-1} - \frac{1 + (-1)^k}{2} \right) + \frac{1 - (-1)^k}{2} $$

$$ = p_k + p_{k-1} - \frac{2 + (-1)^{k+1} + (-1)^k}{2} + \frac{1 - (-1)^k}{2} $$

$p_k + p_{k-1} = p_{k+1}$ であり、$(-1)^{k+1} + (-1)^k = 0$ であるから、

$$ b_{k+2} = p_{k+1} - 1 + \frac{1 - (-1)^k}{2} = p_{k+1} - \frac{1 + (-1)^k}{2} $$

$(-1)^k = (-1)^{k+2}$ なので、

$$ b_{k+2} = p_{k+1} - \frac{1 + (-1)^{k+2}}{2} $$

となり、$n=k+2$ のときも成り立つ。

よって、$n \geqq 2$ のとき $b_n = p_{n-1} - \frac{1 + (-1)^n}{2}$ が示された。 $n=1$ のときは $b_1 = 0$ である。

解法2

(2) の別解

$X_{n+1}$ において '$01$' という配列が現れる条件を考える。 操作規則より、'$0$' は '$1$' に、'$1$' は '$10$' に置き換わる。それぞれの置き換え結果の内部には '$01$' は含まれない。 したがって、新たに '$01$' という配列が生じるのは、置き換え後の文字列が結合される際、前の文字列の末尾が '$0$' であり、かつ後ろの文字列の先頭が '$1$' である場合に限られる。 すべての文字は置き換え後に必ず '$1$' から始まるため、後ろの文字列の先頭は常に '$1$' である。 よって、結合部分で '$01$' が生じるのは、前の文字列の末尾が '$0$' のとき、すなわち元の文字が '$1$' のときのみである。 これは、元の文字列 $X_n$ において「'$1$' の直後に何らかの文字が続く」という状況と一対一に対応する。 ゆえに、$X_{n+1}$ に含まれる '$01$' の回数 $b_{n+1}$ は、$X_n$ に含まれる「末尾以外の '$1$'」の個数に等しい。

$X_n$ に含まれる '$1$' の総数 $o_n$ は、(1) の考察より $o_n = a_{n-1} = p_n$ ($n \geqq 2$) であり、$o_1 = 1 = p_1$ なので、すべての $n \geqq 1$ で $o_n = p_n$ である。 $X_n$ の末尾の数字 $l_n$ は、解法1の考察と同様に、置き換えを繰り返すことで $n$ が奇数のとき '$1$'、$n$ が偶数のとき '$0$' となる。 末尾が '$1$' のとき、後ろに文字が続く '$1$' は $o_n - 1$ 個となる。 末尾が '$0$' のとき、すべての '$1$' の後ろに文字が続くため $o_n$ 個となる。

以上より、 $n$ が奇数のとき：$b_{n+1} = o_n - 1 = p_n - 1$ $n$ が偶数のとき：$b_{n+1} = o_n = p_n$ これをまとめると、$n \geqq 1$ において、

$$ b_{n+1} = p_n - \frac{1 - (-1)^n}{2} $$

となる。$n$ を $n-1$ に置き換えると、$n \geqq 2$ のとき

$$ b_n = p_{n-1} - \frac{1 + (-1)^n}{2} $$

を得る。

解説

文字列の置き換え（L-system などの一種）とフィボナッチ数列が結びつく、非常に有名で美しいテーマの問題である。 (1) では、各文字が次の世代にどのような文字を生み出すかを数えることで、容易に漸化式を立てることができる。 (2) は、単に結果の文字列を眺めるだけでは規則性を見落としやすいが、解法1のように文字列全体の結合法則 $X_{n+2} = X_{n+1} X_n$ を見出すか、解法2のように「どの文字から '$01$' が発生したか」という局所的な生成ルールに遡ることで、明確な論理のもと解答することができる。解法2の方が計算量が少なく、発想として鮮やかである。

答え

(1)

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

(2)

$n=1$ のとき $0$ $n \geqq 2$ のとき

$$ b_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} - \left( \frac{1-\sqrt{5}}{2} \right)^{n-1} \right\} - \frac{1 + (-1)^n}{2} $$