2005年 日本数学オリンピック本選 第２問 解答例
ある整数係数の２変数多項式$${P(x, y)}$$と$${Q(x, y)}$$,
およびある整数$${a_0, b_0}$$に対し
$${a_{n+1}=P(a_n, b_n), b_{n+1} = Q(a_n, b_n)}$$
によって$${a_n, b_n}$$を定めたとき、$${(a_1, b_1) \neq (a_0, b_0)}$$であるが、$${(a_k, b_k) = (a_0, b_0)}$$となる正の整数$${k}$$があるとする。このとき、平面上の２点$${(a_n, b_n)}$$と$${(a_{n+1}, b_{n+1})}$$を両端とする線分上にある、$${x}$$座標、$${y}$$座標がともに整数となる点の個数は$${n}$$によらないことを示せ。
考え方：
$${(a_n, b_n)}$$と$${(a_{n+1}, b_{n+1})}$$を両端とする線分を考えるので、
$${\Delta a_n = a_{n+1} - a_n, \Delta b_n = b_{n+1} - b_n}$$と置いて考えるのが良さそうです。
格子点の数が等しいという条件を
$${\Delta a_n, \Delta b_n}$$の最大公約数が等しいという条件に
読み替えることができれば、
$${P(x, y)}$$と$${Q(x, y)}$$が整数係数多項式であることから
それを証明していけば解決します。
解答例：
各正の整数$${n}$$に対し、$${\Delta a_n = a_{n+1}-a_n, \Delta b_n = b_{n+1}-b_n}$$とおき、
$${\Delta a_n}$$と$${\Delta b_n}$$の両方を割り切る正の整数で最大のものを$${r_n}$$とおく。
$${(a_n, b_n)}$$と$${(a_{n+1}, b_{n+1})}$$を両端とする線分上にあり
$${x}$$座標と$${y}$$座標がともに整数となる点は、
$${k = 0, 1, \cdots r_n}$$を用いて$${(k \Delta a_n / r_n + a_n, k \Delta b_n / r_n + b_n)}$$と表され、
個数は$${r_n+1}$$となる。
よって、$${r_n}$$が$${n}$$によらないこと（$${r_0 = r_1 = \dots}$$）を示せばよい。
$${P(x, y) = \sum_{i, j} p_{ij}x^iy^j, Q(x, y) = \sum_{i, j} q_{ij}x^iy^j}$$とおける。
$${p_{ij}, q_{ij}}$$は整数係数であり、$${i, j}$$は0以上の整数値をとる。
このとき、
$$
\begin{align*}
\Delta a_{n+1}& = a_{n+2} - a_{n+1}\\
&= \sum_{i, j} p_{ij}a_{n+1}^i b_{n+1}^j - \sum_{i, j} p_{ij}a_n^i b_n^j \\
&= \sum_{i, j} p_{ij} \{a_{n+1}^i (b_{n+1}^j - b_n^j) + b_n^j(a_{n+1}^i - a_n^i )) \\
&= \sum_{i, j} p_{ij} \{a_{n+1}^i (b_{n+1}^{j-1} + b_{n+1}^{j-2}b_n + \cdots + b_m^{j-1})(b_{n+1} - b_n) + b_n^j(a_{n+1}^{j-1} + a_{n+1}^{j-2}a_n + \cdots + a_m^{j-1})(a_{n+1} - a_n)\} \\
&= c\Delta a_n + d\Delta b_n \\
\Delta b_{n+1}& = e\Delta a_n + f\Delta b_n \text{(同様の計算により)}\\
\end{align*}
$$
と表せる。$${c, d, e, f}$$は整数である。
これらの式より、$${r_n}$$が$${\Delta a_n, \Delta b_n}$$の公約数であるとき、
$${\Delta a_{n+1}, \Delta b_{n+1}}$$の公約数でもあることは明らか。
よって、正の整数$${l_n}$$を用いて$${r_{n+1} = l_nr_n}$$とおける。
$${(a_k, b_k) = (a_0, b_0)}$$であるから、
$$
\begin{align*}
r_0 &= r_k\\
&= l_{k-1}r_{k-1}\\
&= l_{k-1}l_{k-2}r_{k-2}\\
&\cdots\\
& = l_{k-1}l_{k-2}\cdots l_0r_0\\
\end{align*}
$$
となるが、これを満たすのは$${l_0 = l_1 = \cdots = 1}$$のみ。
よって、$${r_0 = r_1 = \dots}$$が成り立つ
以上より題意は示された。
コメント：
恥ずかしながら、正直かなり苦戦しました。
$${k}$$が必ず偶数になるだろう、とか、
$${P, Q}$$が２次以上では成り立たないだろう、とか、
誤った仮説を立てて証明できないかを探っていたのが原因です。
$${P, Q}$$は無限に次数を増やすことができるので、
問われていること以上の性質はほぼ持たないだろうという感覚があれば、
素直にこの回答にたどり着けるのでしょう。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)