Evolton

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

xとyの2文字からなる文字列znを次の規則(イ),(ロ)で順次定めていく.

(イ) z1=xとおく.

(ロ) znの中に現れるすべてのxをyxで,
すべてのyをxxで置き換えてできる文字列をzn+1とする(n=1,2,3,⋯ ).

例えばz2=yx,z3=xxyx,z4=yxyxxxyxである.
2次の正方行列A,Bに対して,znの中のxをAで,yをBで置き換え,行列の積をつくってできる行列をCnとする.
例えばC1=A,C2=BA,C3=AABA(行列の積)である.

A=(1101),B=(−1001)のとき,
n≧3ならばCn=(−1101)であることを示せ.

難易度7/ 10計算量6/ 10目安25分

行列、数列 帰納的定義の利用、計算整理、数学的帰納法

方針

1回の置換を直接追うと積の順序が複雑になるので、置換を2回まとめる。x↦xxyx、y↦yxyx に対応する行列積を計算すると、それぞれ D と単位行列になる。残りは zn に含まれる x の個数が常に奇数であることを示し、D2=I から結論を得る。

解答

まず、求める行列をD=(−1101)とおく。また単位行列を I とする。

直接計算するとA2=(1201)であり、したがってAABA=(−1101)=Dである。また BABA=I であり、さらに D2=I である。

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

したがって、zn+2 から作られる行列 Cn+2 は、zn の中の各 x を D に、各 y を I に置き換えて積をとったものに等しい。I は積に影響しないので、zn に含まれる x の個数を Xn とすれば Cn+2=DXn である。

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

よって DXn=D であり、すべての n≧1 について Cn+2=D が成り立つ。すなわち n≧3 ならばCn=(−1101)である。

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

別解

解法2

方針

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

解答

x から置換を n−1 回行った語に対応する行列を Xn、
y から同様に作る行列を Yn とする。求める Cn は
Xn である。

置換 x↦yx, y↦xx と積の順序からXn+1=YnXn,Yn+1=Xn2.初期値は X1=A, Y1=B である。したがってX2=BA,Y2=A2,X3=A2BA,Y3=(BA)2.直接計算するとA2BA=(−1101)=D,(BA)2=I.またD2=I.いま (Xn,Yn)=(D,I) ならXn+1=ID=D,Yn+1=D2=I.よって数学的帰納法により n≧3 で常にCn=Xn=D=(−1101).

総評

文字列置換と行列積を組み合わせた、構造把握型の問題。難度は高めで、目安時間は25分前後。1回置換で逐次計算すると見通しが悪いが、2回置換にまとめると x は D、y は単位行列に対応する。最後は x の個数の偶奇だけが残るため、帰納的な個数管理を明確に書くのがよい。 2解法の結論を照合し、条件の必要十分性、端点、符号、定義域、等号成立条件を再確認した。図は論証を補助するものに限定し、縮尺に依存しない式による説明も併記している。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る京大の行列の問題で問題集を作る

出典: 京都大学 1995年度 前期日程 第2次学力試験 第4問。問題文はHTML表示のために再入力・数式組版しています。