おまけの整数問題(2022年 東京大学) | オンライン上での通信制コースをお届けし塾の運営側よりコラム記事などの情報を発信

こんにちは。

オンライン講座の採点をしている稲荷興心です。

8月になりましたが、7月の段階で十分に暑かったのであまり変わりはありませんね。むしろここ数日涼しく、秋になったような感覚さえします。

前回の最後に載せた問題について考えてみたいと思います。書き始めてから説明が難しい部分がたくさんあることに気がつき、容易に手を出してしまったことに後悔しました。問題は以下の通りでした。

数列{a_n}を次のように定める。

a₁=1,  a_n+1=a_n²+1  (n=1, 2, 3・・・)

(1)正の整数nが3の倍数のとき、a_nは5の倍数となることを示せ。

(2)k, nを正の整数とする。a_nがa_kの倍数となるための必要十分条件をk, nを用いて表せ。

(2022年　東京大学・理科 大問2 (3)を割愛)

まずはa_nがどうなっているかについて調べてみることにしましょう。こういった作業は問題を解く上で必須ですが、今回は難しいです。nが6を超えたあたりから計算するのが非常に面倒になります(Excelで計算したのですが、有効数字15桁までしか表示されず驚きました)。また素因数についても調べてみると、それにも難儀します(こちらのページを活用しました)。またn=7まで調べた感じでは、予想できるほど情報が得られませんでした。

Excelや電卓を使うような作業は試験会場ではできないため(笑)、限られた情報からa_nがどういった法則に則っているのかを見抜く必要があります。大問が小問に分かれているときは誘導になっている場合が多いので、まずは(1)について考えてみることにしましょう。

(1)  の解答

a₁=1, a₂=2, a₃=5であるため、n=3でa_nは5の倍数になっている。

またn=3k (kは自然数)でa_nは5の倍数であると仮定すると、

a_3k+3=a_3k+2²+1=(a_3k+1²+1)²+1={(a_3k²+1)²+1}²+1={a_3k⁴+2a_3k+2}²+1≡2²+1≡0 (mod 5)

よってn=3k+3においてもa_nは5の倍数であるため、数学的帰納法によりnが3の倍数のとき、a_nは5の倍数となることが示された。

この結果から何が予想されるでしょうか。もう少し考えるために、(1)の結果ともう２つ簡単に得られる結果をまとめておきましょう。

i)a₁=1であるため、a₁は全てのa_nの約数になっている

ii)nが偶数のときa_nも偶数で、なおかつa₂=2である(これも数学的帰納法により示せます)

→nが偶数のとき、a_nはa₂を約数にもつ

iii)nが3の倍数のときa_nは5の倍数で、なおかつa₃=5である

→nが3の倍数のとき、a_nはa₃を約数にもつ

少し状況が整理されてきました。この情報から「a_nがa_kの倍数となる」ときはどういったときであるかについて予想してみることにしましょう。

このi)~iii)の情報から予想される結論の一つは以下のようになっていると考えられます。

「nがkの倍数のとき、a_nはa_kの倍数となる」―①

あとはこの結論が正しいと願いながら証明してみることになりますが、これがなかなか難しいです。また(2)の問題文を読むと、「必要十分条件を〜表せ」とあるので①だけでなく、その逆である「a_nがa_kの倍数のとき、nはkの倍数である」についても示さないといけません。つまり、「nがkの倍数でないとa_nはa_kの倍数にはならない」ことも論証に盛り込む必要があります。

この目標を達成するためにはmを任意の自然数としてa_m≡a_k+m  (mod a_k)であることを示せばよいのですが、これを理解するのに苦労しました。

漸化式からa_nはnに伴って単調に増加するため、m<kでは0<a_m<a_kとなり、a_m≢0 (mod a_k)です。ここでa_m≡a_k+m  (mod a_k)が成り立つとしてみると、m=kのとき0≡a_k≡a_2k(mod a_k)となり、m=2k, 3k, ・・・と続けていくと任意の自然数lに対してa_lk≡0 (mod a_k)であることがわかります。また0<m<kにおいてはa_m≢0 (mod a_k)となるので、同様の議論によりnがkの倍数でないときはa_n≢0 (mod a_k)であることがわかります。

なので任意の自然数mに対してa_m≡a_k+m  (mod a_k)が成り立つことを示すことが、nがkの倍数であることがa_nがa_kの倍数となるための必要十分条件であることを示すのと同じであるということがわかりました。

では実際に解答を書いてみましょう。

(2)の解答

a_k+1=a_k²+1≡1=a₁ (mod a_k)であり、ある自然数mにおいてa_m+k≡a_m  (mod a_k)であると仮定する。

このとき、

a_k+m+1=a_k+m²+1≡a_m²+1=a_m+1  (mod a_k)

であることからm+1においてもa_m+k+1≡a_m  (mod a_k)が成り立つので、数学的帰納法によりすべての自然数mに対してa_m+k≡a_m (mod a_k)が成り立つことが示された。

ここでa₁=1>0であり、a_nはnに伴って単調に増加するのでm<kのとき0<a_m<a_kとなり、a_m≢0 (mod a_k)である。

つまりm=1, 2, ・・・, k-1においてa_m+k≡a_m ≢0 (mod a_k)となる。

またm=kにおいてa_2k≡a_k ≡0 (mod a_k)となる。

これを繰り返すことで、

・nがkの倍数でないときはa_n≢0 (mod a_k)

・nがkの倍数のときはa_n≡0 (mod a_k)

となることがわかる。

よって求める必要十分条件はnがkの倍数であることである。

正直なところ、高2生までは解答を読んで理解できればそれで十分な問題だったと思います。ただ、東大は毎年難しい問題が並んでいるうえに、この問題が出題された年においてこれが一番難しい問題というわけでもなかったので合格するためには解いておきたい問題かもしれません。こういった問題を解けるようになるためには知識が定着していることはもちろん、それに加えて発想を引っ張り出す手段を知らなければいけません。

この手段を習得するための演習ではそれまで学んできたことをどのように活用するのかについて考えることになるので、高校数学における一番楽しい部分であると個人的に思っています。そういったことから、この一連のブログの最初において演習1の問題を選んでいることを書いていましたが、楽しく勉強できるようなテキストを作成できたら、と考えています。今のところ、オンライン講座にこのテキストが反映されるかはわかりませんが、既存の演習のテキストも非常に良いので、高校数学を一通り学んだのちに活用していただけると嬉しいなと思っています。