Evolton

横浜国立大学 2018年度 前期理系数学 第4問

c を 5 で割り切れない 2 以上の整数とする。数列 {an},{bn} は以下の条件をみたす。

(i) an (n=1,2,3,…) は 0,1,…,c−1 のいずれかである。

(ii) bn はb1=1,cbn+1=5an+bn(n=1,2,3,…)をみたす整数である。

次の問いに答えよ。

(1) c=3 のとき、an,bn (n=1,2,3,…) を求めよ。

(2) n=1,2,3,… に対して、0<bn<5 を示せ。

(3) c=5l+4(l は 0 以上の整数)のとき、an,bn (n=1,2,3,…) を求めよ。

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

数列、整数 剰余分類、数学的帰納法、漸化式の変形、場合分け

方針

c と 5 が互いに素であることから、cbn+1=5an+bn の割り切れ条件で an が一意に定まる。(2) は 0<bn<5 を仮定して次の bn+1 が 1,2,3,4 に入ることを帰納法で示す。(3) は c≡−1(mod5) を使って bn の交代を出す。

解答

(1)
c=3 のとき、3bn+1=5an+bn であり、an は 0,1,2 のいずれかである。よってan≡bn(mod3)をみたす an が一意に定まる。b1=1 から(a1,b2)=(1,2),(a2,b3)=(2,4),(a3,b4)=(1,3),(a4,b5)=(0,1)となるので、以後これを繰り返す。したがって(an,bn)={(1,1)(n≡1(mod4)),(2,2)(n≡2(mod4)),(1,4)(n≡3(mod4)),(0,3)(n≡0(mod4))である。

(2)
c は 5 で割り切れないから、5 と c は互いに素である。したがって 5an+bn が c で割り切れるような an∈{0,1,…,c−1} は一意に定まる。

0<bn<5 と仮定する。このとき 0≦an≦c−1 より0<5an+bn<5cである。さらに 5an+bn=cbn+1 であるから、bn+1 は整数で0<bn+1<5をみたす。b1=1 であるから、数学的帰納法によりすべての n で0<bn<5である。

(3)
c=5l+4 のとき c≡−1(mod5) である。cbn+1=5an+bn を 5 で割った余りで見ると−bn+1≡bn(mod5)である。(2)より bn,bn+1 は 1,2,3,4 のいずれかなので、bn+1 は 5−bn に等しい。b1=1 からbn={1(n が奇数),4(n が偶数)である。

したがって、n が奇数のときan=cbn+1−bn5=4c−15=4l+3であり、n が偶数のときan=cbn+1−bn5=c−45=lである。よって(an,bn)={(4l+3,1)(n が奇数),(l,4)(n が偶数)である。

別解

解法2

方針

各 bn∈{1,2,3,4} に対し、合同式 5an≡−bn(modc) の唯一の代表 0≦an<c を選ぶ「状態遷移」として数列を見る。(1)は4状態の表、(3)は2状態の直接計算で周期を確定する。

解答

(1)

c=3 のとき5an+bn≡0(mod3)である。5≡2(mod3) だからan≡bn(mod3).後の (2) と同じ評価から bn∈{1,2,3,4} であり、各状態の遷移はbnanbn+1112224413301となる。b1=1 からこの表をたどれば(an,bn)={(1,1)(n≡1(mod4)),(2,2)(n≡2(mod4)),(1,4)(n≡3(mod4)),(0,3)(n≡0(mod4)).(2)

5∤c なので gcd⁡(5,c)=1 である。したがって、各整数 bn に対して5an≡−bn(modc)を満たす an∈{0,1,…,c−1} はただ1つ存在する。

いま 1≦bn≦4 とする。すると0<5an+bn≦5(c−1)+4=5c−1<5c.しかも 5an+bn=cbn+1 だから0<bn+1<5.初項 b1=1 から帰納的に0<bn<5がすべての n で成り立つ。

(3)

c=5l+4 とする。bn=1 のとき5(4l+3)+1=20l+16=4cだから、一意性によりan=4l+3,bn+1=4.一方、bn=4 のとき5l+4=cだからan=l,bn+1=1.初項が b1=1 なので、この2状態が交互に現れる。よって(an,bn)={(4l+3,1)(n が奇数),(l,4)(n が偶数).なお0≦l<c,0≦4l+3<5l+4=cなので、得られた an は指定された範囲にも入っている。

総評

難度6、計算量6。想定時間は20分程度。割り切れ条件から an の一意性を押さえ、bn が常に 1 から 4 の範囲に入ることを帰納法で示すのが山場である。(3) では c≡−1(mod5) から bn が交代することに気づけば短くまとまる。別解では状態ごとの遷移を直接検算し、最後に得られた an が必ず 0≦an<c を満たすところまで確認した。

大学別の過去問PDF

問題編・解答編セット/買い切り

Evolton Pro

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

冊子PDFで見る横国の数列の問題で問題集を作る

出典: 横浜国立大学 2018年度 前期 理系数学 第4問(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。