Evolton

東京大学 1982年度 前期日程 第2次学力試験文系数学 第4問

行列A=(12−1201),B=(10−1212)を考える。xy 平面上の点 P0=(1,1) から始め、点列 P0,P1,P2,… を次の手続きで定める。Pn=(xn,yn) とする。

(イ) xn+yn≧1100 のときは、(xn+1yn+1)=A(xnyn)または(xn+1yn+1)=B(xnyn)のいずれかを選ぶ。

(ロ) xn+yn<1100 のときは、(xn+1yn+1)=A(xnyn)とする。

(1) P2 として可能な点をすべて求め、図示せよ。

(2) xn+yn を n で表せ。

(3) P10 として可能な点は何個あるか。

難易度6/ 10計算量5/ 10目安28分

行列、数列、場合の数 漸化式の変形、数え上げ、必要十分条件

方針

和 sn=xn+yn に注目すると、行列 A,B のどちらを使っても sn+1=12sn になる。(1)は2回分を直接列挙する。(3)は sn がしきい値以上である間だけ2択があり、n=0 から 7 までの8回が自由であることを確認する。さらに、各選択列が異なる点を与えることを x 座標の二進的な変化量で示す。

解答

(1) A(11)=(01),B(11)=(10).さらにA(01)=(−1/21),B(01)=(01/2),A(10)=(1/20),B(10)=(1−1/2).したがってP2=(−12,1), (0,12), (12,0), (1,−12)の4点である。

(2)
sn=xn+yn とおく。A,B のどちらを選んでも、成分を加えるとsn+1=12sn.s0=2 だからxn+yn=sn=21−n.(3)s7=164≧1100,s8=1128<1100.よって n=0,1,…,7 の8回だけ A,B を自由に選べ、以後は A に決まる。

時刻 n に A を選ぶとxn+1=xn−sn2=xn−2−n,B を選ぶと xn+1=xn である。したがって P8 の x 座標は1−∑n∈E2−n(E⊂{0,1,…,7})と表される。有限二進表示の一意性により、256個の部分集合はすべて異なる x 座標を与える。最後の2回に使う A は行列式が 1/2 で、異なる点を異なる点へ移す。ゆえに256個である。

別解

解法2(和と差の座標)

方針

sn=xn+yn、dn=xn−yn を用いる。和は毎回半減し、自由選択期間には差が符号付き二進数として変化する。異なる符号列が異なる差を与えることから個数を示す。

解答

(1)
直接計算によりP2=(−12,1), (0,12), (12,0), (1,−12).(2)
sn=xn+yn とおけば、どちらの操作でもsn+1=12sn.よってsn=21−n.(3)
dn=xn−yn とおく。A を選ぶとdn+1=dn−sn2,B を選ぶとdn+1=dn+sn2.sn/2=2−n、d0=0 だから、自由な8回の後にはd8=∑n=07εn2−n,εn∈{−1,1}.二つの符号列が初めて異なる最大の重みを 2−k とする。その項による差は 21−k であり、それより後の項による差の絶対値の総和は 21−k−2−6 未満である。したがって相殺は起こらず、256個の符号列はすべて異なる d8 を与える。

s8 は共通なので P8 も256個である。以後の2回の A は1対1の変換だからP10 は 256個である。

総評

難度6、計算量5、目安28分。和 xn+yn はどちらの操作でも半減し、自由選択は8回だけである。単に 28 とせず、有限二進表示または差の符号付き二進表示により、異なる選択列が異なる点を与えることまで示した。

Evolton Pro

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

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

出典: 東京大学 1982年度 前期 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。