Evolton

東京大学 2014年度 前期日程 第2次学力試験理系数学 第5問

rを0以上の整数とし,数列{an}を次のように定める。a1=r,a2=r+1,an+2=an+1(an+1)(n=1, 2, 3, ⋯ )また,素数pを1つとり,anをpで割った余りをbnとする。
ただし,0をpで割った余りは0とする。

(1) 自然数nに対し,bn+2はbn+1(bn+1)をpで割った余りと一致することを示せ。

(2) r=2,p=17の場合に,10以下のすべての自然数nに対して,bnを求めよ。

(3) ある2つの相異なる自然数n,mに対して,bn+1=bm+1>0,bn+2=bm+2が成り立ったとする。このとき,bn=bmが成り立つことを示せ。

(4) a2, a3, a4, ⋯にpで割り切れる数が現れないとする。
このとき,a1もpで割り切れないことを示せ。

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

数列、整数 合同式、剰余分類、帰納的定義の利用、背理法

方針

(1) から (3) は文科第4問と同じく、余りだけで漸化式を追い、非零の共通余りを素数 p のもとで割り戻す。(4) は背理法を用いる。もし a1 が p で割り切れるなら b1=0、一方で仮定から bk>0 が k≧2 で成り立つ。有限個しかない正の余りの隣接ペア (bk,bk+1) を考えると同じペアが現れるので、(3) を1つずつ過去へ戻して b1 が後の正の余りに等しいという矛盾を導く。

解答

(1) bn は an を p で割った余りであるから an≡bn(modp),an+1≡bn+1(modp) である。したがって an+1≡bn+1(modp) であり、積をとって an+1(an+1)≡bn+1(bn+1)(modp) を得る。

漸化式より an+2=an+1(an+1) であるから、an+2 を p で割った余り bn+2 は、bn+1(bn+1) を p で割った余りと一致する。

(2) r=2 より b1=2,b2=3 である。(1) を用いて順に計算する。 b3≡3(2+1)=9(mod17) より b3=9 である。 b4≡9(3+1)=36≡2(mod17) より b4=2 である。 b5≡2(9+1)=20≡3(mod17) より b5=3 である。

ここで (b4,b5)=(2,3)=(b1,b2) となったので、以後は同じ計算が繰り返される。したがってn12345678910bn2392392392である。

(3) bn+1=bm+1>0,bn+2=bm+2 とする。c=bn+1=bm+1 とおくと、c は p で割った余りであり、0<c<p である。

(1) より bn+2≡c(bn+1)(modp) であり、同様に bm+2≡c(bm+1)(modp) である。bn+2=bm+2 だから c(bn+1)≡c(bm+1)(modp) すなわち c(bn−bm)≡0(modp) である。 p は素数で、0<c<p だから c は p で割り切れない。よって bn−bm≡0(modp) である。bn,bm はどちらも 0 以上 p−1 以下なので bn=bm である。

(4)

背理法で示す。a1 が p で割り切れると仮定する。このとき b1=0 である。一方、問題の仮定より a2,a3,a4,… には p で割り切れる数が現れないので bk>0(k≧2) である。 k≧2 について、隣接する2つの余りの組 (bk,bk+1) を考える。各成分は 1,2,…,p−1 のいずれかであるから、このような組は高々 (p−1)2 通りしかない。したがって無限に続く組 (b2,b3),(b3,b4),(b4,b5),… の中には、同じ組が2回現れる。すなわち、ある 2≦n<m が存在して bn=bm,bn+1=bm+1 となる。

ここで bn=bm>0 かつ bn+1=bm+1 であるから、(3) を添字 n−1,m−1 に適用すると bn−1=bm−1 が従う。さらに bn−1>0 であれば、同じ議論を1つ前の添字に繰り返せる。n≧2 なので、この操作を順に行うと b1=bm−n+1 を得る。

ところが m−n+1≧2 であるから、仮定より bm−n+1>0 である。一方、最初に仮定した通り b1=0 である。これは矛盾である。

したがって a1 は p で割り切れない。すなわち a1 も p で割り切れない である。

総評

難度7、計算量6。目安時間は28分。(1) から (3) は剰余漸化式の基本操作だが、(4) は有限性と逆向き一意性を組み合わせる発想が必要である。a2 以降が p で割り切れないという仮定から、bk>0 の隣接ペアが有限集合内を動くと見る。重複したペアを見つけた後、(3) を過去方向へ反復して b1=0 と後の正の余りが等しい矛盾に持ち込むのが採点上の核心である。

Evolton Pro

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

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

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