cccpcamera blog

　東大の入試問題は、例年、良問が出題される。真面目に受験勉強に取り組んでいて、かつ、柔軟な思考ができないと無理だろう。もともと頭の良い子がまじめに勉強して、初めて合格するのですよ、と言っているような感じがします。
　
　問2は思考力が問われる問題。
　
問2　　問題
数列　{a(n)}　を以下のように定める。（累乗を＾と書きます）
a(1)=1 a(n+1)=a(n)^2+1
(1)　正の数nが3の倍数のとき、a(n)は5の倍数であることを示せ。
(2)　k,nを正の整数とする。a(n)がa(k)の倍数であるための、必要十分条件をk,nを用いて表せ。
(3)　a(2022)とa(8091)^2の最大公約数を求めよ

解答方針
　(1)は数学的帰納法で簡単にできる。(2)は考えないとできないが、(1)を取り組んだ過程でおのずから解答方針が見えるだろう。東大に入るには、このくらいできないとだめだよと言っているような問題ですね。(3)は(1)(2)がヒントになっていることはわかるでしょう。(1)で5の倍数であることを示したけれど、このほかに25の倍数でないことを示しておかないと(3)はできない。その点で、ちょっとヒントが少なくて、完答はたいへん。

解答
　(1)　簡単なので省略
　(2)　a(k)=a と書く。B(l)をaの倍数とする。
a(k)はaの倍数だから、a(k)=B(0)と書くことができる。
a(k+1)=B(0)^2+1= B(0)^2+a(1)であるから、a(k+1)=B(1)+a(1)と書くことができる。
同様にして、a(k+m)=B(m)+a(m) (m=1,2,・・・,k-1)と書くことができる。
ここで、m=1,2,・・・,k-1のときa(m)<aであるから、a(m)はaの倍数ではないので、a(k+m)はaの倍数ではない。
次に、
a(k+k)={B(k-1)+a(k-1)}^2+1= B(k-1){ B(k-1)+2* a(k-1)}+a(k)となる。
よって、a(k+k)はaの倍数である。
同様にして、nがkの倍数のとき、a(n)はaの倍数となり、それ以外では倍数とならない。

（この書き方では点をひかれそうと思うならば、以下のように書くと良い。）
Nを正の整数とする。a(Nk)がaの倍数とし、a(Nk)=B(0)と書く。あとは同じ。

　(3)ｋを正の整数とする。a(3k)は(1)より５の倍数である。
次に、a(3k+3)が25の倍数でないことを示す。
a(3k)は5の倍数なのだから、a(3k+3)は25の倍数に5を足した値になる。よって、a(3k+3)は5の倍数であって、25の倍数ではない。
すなわち、a(2022)は5の倍数であって、25の倍数ではない。
一方、a(8091)=a(2022*4+3)であるから、a(8091)はa(2022)の倍数に５を足した値である。
a(2022)＝5Cと書く。Cは5の倍数ではない。
このとき、a(8091)^2＝25(CN+1)　と書ける。ただし、Ｎは整数。
以上より、求める最大公約数は5