京都大学 1995年度 前期日程 第2次学力試験理系数学 第4問

まず、求める行列を$$D=\left(\begin{array}{cc}-1& 1\\ 0& 1\end{array}\right)$$とおく。また単位行列を $I$ とする。

直接計算すると$$A^2=\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)$$であり、したがって$$AABA=\left(\begin{array}{cc}-1& 1\\ 0& 1\end{array}\right)=D$$である。また $BABA=I$ であり、さらに $D^2=I$ である。

次に、文字列の置換を2回続けて見る。1回の置換では $x\mapsto yx,y\mapsto xx$ であるから、2回続けると $x\mapsto xxyx,y\mapsto yxyx$ である。行列積に直すと、$xxyx$ は $AABA=D$、$yxyx$ は $BABA=I$ に対応する。

したがって、$z_{n+2}$ から作られる行列 $C_{n+2}$ は、$z_n$ の中の各 $x$ を $D$ に、各 $y$ を $I$ に置き換えて積をとったものに等しい。$I$ は積に影響しないので、$z_n$ に含まれる $x$ の個数を $X_n$ とすれば $C_{n+2}=D^{X_n}$ である。

あとは $X_n$ が常に奇数であることを示せばよい。$z_n$ に含まれる $y$ の個数を $Y_n$ とすると、置換規則より $X_{n+1}=X_n+2Y_n$ である。右辺の第2項 $2Y_n$ は偶数なので、$X_{n+1}$ と $X_n$ の偶奇は同じである。$X_1=1$ だから、すべての $n$ について $X_n$ は奇数である。

よって $D^{X_n}=D$ であり、すべての $n\geqq 1$ について $C_{n+2}=D$ が成り立つ。すなわち $n\geqq 3$ ならば$$C_n=\left(\begin{array}{cc}-1& 1\\ 0& 1\end{array}\right)$$である。

置換を行列対の漸化式で追う

文字 $x,y$ から出発した置換語に対応する行列をそれぞれ
$X_n,Y_n$ と置く。置換規則から得る2本の積漸化式を使い、
$n=3$ で $(D,I)$ になった後は同じ組が保たれることを示す。

$x$ から置換を $n-1$ 回行った語に対応する行列を $X_n$、
$y$ から同様に作る行列を $Y_n$ とする。求める $C_n$ は
$X_n$ である。

置換 $x\mapsto yx,y\mapsto xx$ と積の順序から$$X_{n+1}=Y_n{X}_n,Y_{n+1}=X_n^2\mathrm{.}$$初期値は $X_1=A,Y_1=B$ である。したがって$$X_2=BA,Y_2=A^2,$$$$X_3=A^{2}BA,Y_3=(BA{)}^2\mathrm{.}$$直接計算すると$$A^{2}BA=\left(\begin{array}{cc}-1& 1\\ 0& 1\end{array}\right)=D,(BA{)}^2=I\mathrm{.}$$また$$D^2=I\mathrm{.}$$いま $(X_n,Y_n)=(D,I)$ なら$$X_{n+1}=ID=D,Y_{n+1}=D^2=I\mathrm{.}$$よって数学的帰納法により $n\geqq 3$ で常に$$C_n=X_n=D=\left(\begin{array}{cc}-1& 1\\ 0& 1\end{array}\right)\mathrm{.}$$