トップ› 京都大学› 1995年› 理系第4問

京都大学 1995年理系第4問解説

方針・初手

文字列の長さは $n$ とともに指数的に増加するため、直接すべての文字列を書き下して行列を計算することは不可能です。そこで、文字列 $z_n$ の構成規則から、$z_n$ に関する漸化式を導き出すことを考えます。「規則に従って文字を置き換える」という操作は、文字列を分割してからそれぞれ置き換えて結合しても結果が変わらないという性質を持っています。これを利用して $z_{n+2}$ を $z_{n+1}$ と $z_n$ で表す関係式を見つけ、それを行列の漸化式に翻訳して数学的帰納法を用います。

解法1

文字列の置き換え規則を写像 $f$ として表す。すなわち、任意の文字または文字列 $S, T$ に対して

$$ f(x) = yx, \quad f(y) = xx, \quad f(ST) = f(S)f(T) $$

と定義する。このとき、数列 $\{z_n\}$ は $z_1 = x, \ z_{n+1} = f(z_n)$ と表せる。ここで、すべての自然数 $n$ について

$$ z_{n+2} = z_n z_n z_{n+1} \quad \cdots (*) $$

が成り立つことを、数学的帰納法を用いて示す。

(i)

$n=1$ のとき $z_1 = x$ $z_2 = f(z_1) = yx$ $z_3 = f(z_2) = f(yx) = f(y)f(x) = (xx)(yx) = xxyx$ 一方、右辺は $z_1 z_1 z_2 = x \cdot x \cdot yx = xxyx$ となり、両辺は一致する。よって $n=1$ のとき $(*)$ は成立する。

(ii)

$n=k$ のとき $(*)$ が成り立つと仮定する。すなわち

$$ z_{k+2} = z_k z_k z_{k+1} $$

この両辺に $f$ を施すと、文字列の結合は保たれるため

$$ f(z_{k+2}) = f(z_k z_k z_{k+1}) = f(z_k) f(z_k) f(z_{k+1}) $$

定義より $f(z_m) = z_{m+1}$ であるから

$$ z_{k+3} = z_{k+1} z_{k+1} z_{k+2} $$

となり、$n=k+1$ のときも $(*)$ は成立する。

以上より、すべての自然数 $n$ について $(*)$ が成り立つ。文字列の連結は、対応する行列の積となるため、行列 $C_n$ についても同様に

$$ C_{n+2} = C_n C_n C_{n+1} = C_n^2 C_{n+1} \quad \cdots (**) $$

が成り立つ。

与えられた行列 $A, B$ を用いて、$C_1, C_2, C_3, C_4$ を計算する。 $C_1 = A$ $C_2 = BA$

$$ C_2^2 = (BA)^2 = \begin{pmatrix} -1 & -1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} -1 & -1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = E \quad (\text{単位行列}) $$

$$ C_3 = C_1^2 C_2 = A^2 (BA) = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} -1 & -1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} -1 & 1 \\ 0 & 1 \end{pmatrix} $$

この行列を $M$ とおくと、$C_3 = M$ である。ここで $M^2$ を計算すると

$$ M^2 = \begin{pmatrix} -1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} -1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = E $$

さらに

$$ C_4 = C_2^2 C_3 = E M = M $$

となる。

最後に、$n \ge 3$ のとき $C_n = M$ であることを、数学的帰納法を用いて示す。 (I)

$n=3, 4$ のときは、上記より $C_3 = M, C_4 = M$ であり成立する。 (II)

$k \ge 3$ とし、$n=k, k+1$ のときに $C_k = M, C_{k+1} = M$ であると仮定する。漸化式 $(**)$ より

$$ C_{k+2} = C_k^2 C_{k+1} = M^2 M = E M = M $$

よって、$n=k+2$ のときも成立する。

（I）, （II）より、すべての $n \ge 3$ について $C_n = \begin{pmatrix} -1 & 1 \\ 0 & 1 \end{pmatrix}$ となることが示された。（証明終）

解説

具体的な文字列の長さが急激に増大していくため、まともに代入して計算するのは不可能であることに早く気づく必要があります。このような「文字列の書き換え操作（L-systemなどに似た生成規則）」では、文字列の間に漸化式が隠れていることがほとんどです。実験として $z_1, z_2, z_3, z_4$ あたりまでを書き下し、$z_3 = z_1 z_1 z_2$ というパターンの発見から一般項の推測へ繋げるのが正攻法です。漸化式さえ見つけてしまえば、あとは行列の性質（ある程度の累乗で単位行列になる等）を利用して周期性に持ち込むだけの平易な帰納法の問題に帰着します。