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

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

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

問題１. $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_0$ を $3$ を法として分類してみる。

ある $n$ で $a_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)$ となる平方数は存在しないことがわかる。そのため、一旦ある $n$ で $a_n \equiv 2 (\mod 3)$ となると、それ以降この数列に平方数は現れない。したがって、 $a_n$ より後はすべて単調増加となるので、明らかに題意を満たさない。この観察結果から、 $a_n$ が $3$ を法としたときに、どのグループに属するかを考えていけばよさそうだと指針がたてられる。

$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
　正の整数列に上限と下限が存在するので、鳩ノ巣原理より少なくとも１つの自然数 $A$ が存在して、 $a_n=A$ となる $n$ が無数に存在する。
　以上より、 $a_0$ が３の倍数の場合は題意を満たす。

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

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