流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【IMO2017】2017年国際数学オリンピックの問題1【解答・解説】

2017年国際数学オリンピック(IMO2017)の問題1 

 なんとなく数学オリンピックの今年の問題を解いてみたくなったので挑戦してみた。問題は、数学オリンピック財団のサイト(http://www.imojp.org/challenge/)を参照しました。今回は、問題1の解答と解説をしていく。もし間違えていたら、優しく指摘してれると助かります。それと、もっと良い解法を教えてくれたら喜びます。
 では、問題を見てみましょう。

問題1. a_0 \gt 1をみたすような各整数a_0に対して、数列a_0,a_1,a_2,...を以下のように定める:
a_{n+1}= \{ \sqrt{a_n}      \sqrt{a_n}が整数のとき、
      \{ a_n+3  そうでないとき、    n=0,1,2,...
このとき、あるAが存在してa_n=Aをみたすnが無数にあるようなa_0をすべて求めよ。

まずは観察と場合わけから

 問題の数列の作り方は、平方数になったときだけルートをとり、それ以外は3を足していくことで作られている。慣れるために、いくつかの例でためしてみよう。

a_0=2のとき、2,5,8,11,...
a_0=3のとき、3,6,9,3,...
a_0=4のとき、4,2,5,8,...
a_0=5のとき、5,8,11,14,...
a_0=6のとき、6,9,3,6,...

という具合になる。3ずつ増えていくという特徴を活かすために、まずはa_03を法として分類してみる。

あるna_n \equiv 2(\mod 3)となる場合

 まずは、平方数を調べる。
 0^2 \equiv 0 (\mod 3)
 1^2 \equiv 1 (\mod 3)
 2^2 =4 \equiv 1 (\mod 3)
より、N \equiv 2(\mod 3)となる平方数は存在しないことがわかる。そのため、一旦あるna_n \equiv 2 (\mod 3)となると、それ以降この数列に平方数は現れない。したがって、a_nより後はすべて単調増加となるので、明らかに題意を満たさない。この観察結果から、a_n3を法としたときに、どのグループに属するかを考えていけばよさそうだと指針がたてられる。

a_0 \equiv 0 (\mod 3)の場合

 次は、a_0 \equiv 0 (\mod 3)の場合を考える。この場合は、任意のnに対してa_n \equiv 0(\mod 3)であることが示せる。
 実際、a_nが3の倍数なら、a_n+3も3の倍数である。
 また、a_nが平方数の場合は、k自然数としてa_n=k^2とおくと、素因数分解の一意性からある自然数lを用いてk=3lと表せる。したがって、この場合もa_{n+1}=3l \equiv 0 (\mod 3)となる。
 a_0 \equiv 0 (\mod 3)の場合は、a_n \equiv 2 (\mod 3)の場合とは異なり、数列 \{ a_n \}には明らかな上限a_0^2が存在する。*1
 正の整数列に上限と下限が存在するので、鳩ノ巣原理より少なくとも1つの自然数Aが存在して、a_n=Aとなるnが無数に存在する。
 以上より、a_0が3の倍数の場合は題意を満たす。

a_0 \equiv 1(\mod 3)の場合

最後に、a_0 \equiv 1(\mod 3)の場合を考える。数列を順番に作っていき、あるna_n \equiv 2(\mod 3)となれば、上に書いた証明から題意を満たさない。
そこで、すべてのnについて、a_n \equiv 1(\mod 3)となるa_0が存在すると仮定する。(以下でこの仮定から矛盾を導き、背理法により、いつか必ずあるna_n \equiv 2(\mod 3)となることを証明する。)
 今回は、平方数の最小性に着目した証明方法をとることにした。
まず \{ a_n \}の内、最小の平方数をl^2とおく。l^2より小さな平方数は存在しないので、数列の定義から、l^2の次の数列であるl \{ a_n \}の最小値となる。ここで、l^2の最小性から、ll^2の間に、a_n \equiv 1であるような数は存在しないはずである。ところが、次に示すように、そのような数を構成することができてしまうのだ。
 仮定より、lはある自然数mを用いてl=3m+1 (m \ge 2)と表せる。*2ここで、以下に定義する平方数Lを考える。

 L:= \{ 3(m-1)+1 \}^2=(3m-2)^2

この平方数Lは、明らかにl^2より小さい。また、

L-l=(3m-2)^2-(3m+1)
=9m^2-15m+3
 \gt 9m^2-15m
=9m(m-\frac{5}{3})
より、m \ge 2であるから、平方数L \equiv 1 (\mod 3)

l \lt L \lt l^2

を満たすが、このことは、l^2が最小の平方数であることに反する。
よって、背理法により、a_0 \equiv 1(\mod 3)の場合、あるna_n \equiv 2(\mod 3)となるので、題意を満たさない。

解答

以上をまとめて、題意を満たすa_0は『3の倍数』である。

*1:a_n3ずつ増加していくためa_0^2を"飛ばして"a_0^2より大きくなることができない。また、a_0^2まで増加できたとしても、定義よりa_{n+1}a_nより小さくなる。

*2:lが平方数でないことから、l=4の場合つまりm=1は仮定に反する。