ISL 2016 N5 証明と発想

ISL 2016 N5 解いていきます。証明をまず書いてからその後発想について書きます。

証明

$ X_{k,a}=\{(x,y)~|~k=\dfrac{x^2-a}{x^2-y^2},x,y\in\mathbb{Z}_{ \geq 0 }\}$とする。

$(x,y) \in X_{k,a},x>\sqrt{a}$となるものが存在する。
$ \Longleftrightarrow (x,y) \in X_{k,a},0≦x<\sqrt{a}$となるものが存在する。
この同値を示せば題意を示したことになるが
$k$は正であるから、
$x>\sqrt{a}\Longleftrightarrow x^2-a>0 \Longleftrightarrow x^2-y^2>0 \Longleftrightarrow x>y$である。同様にすると
$0≦x<\sqrt{a} \Longleftrightarrow x< y$であるから
$(x,y) \in X_{k,a},x>y$となるものが存在する。
$ \Longleftrightarrow (x,y) \in X_{k,a},x< y$となるものが存在する。$\cdots(ii)$この同値を示せば良い。

$(ii)$の$ \Longleftarrow $の証明

$x< y$となる$(x,y)\in X_{k,a}$において補題より
$(x',y')=((2k-1)x+2ky,(2k-2)x+(2k-1)y)\in X_{k,a}$
$x'-y'=x+y>0 \Longrightarrow x'>y'$であるから証明終了。

$(ii)$の$ \Longrightarrow $の証明

$x>y$となる$(x,y)\in X_{k,a}$のうち$x$が最小となるものを取る。補題より
$(x',y')=(|(2k-1)x-2ky|,|(2k-2)x-(2k-1)y|)\in X_{k,a}$
$ x'>y'$と仮定する。
$(2k-1)x-2ky \geq 0$のとき
$ (k-1)x^2-ky^2=-a<0$であるから
$x'-x=2((k-1)x-ky)<2(\dfrac{ky^2}{x}-ky)=2ky(\dfrac{y}{x}-1) \leq 0$
$ \Longleftrightarrow x'< x$
$(2k-1)x-2ky<0$のとき
$ x'-x=2k(y-x)<0$
$ \Longleftrightarrow x'< x$
よって$(x',y')\in X_{k,a},x'>y',x'< x$となるがこれは$x$の最小性に矛盾する。
よって$x' \leq y'$特に$x'=y'$では無いから$x'< y'$である。
以上より$(ii)$の同値を示せた。

発想

補題の恒等式の発想

まず分母払って整理したら$ (k-1)x^2-ky^2=-a$
で$k,a$を定数としてみたときペル方程式っぽいって感じ、、まずペル方程式の場合から考えてみる。特に$x^2-2y^2=1$の整数解を考える。ブラーマグプタの恒等式から$x^2-2y^2=(x^2-2y^2)(3^2-2･2^2)=(3x+4y)^2-2(2x+3y)^2$が成り立つから$(x,y)$が解なら$(3x+4y,2x+3y)$も解となる。こんな感じでこの問題もできそうと考えた。$(a^2+nb^2)(c^2+nd^2)=(ac-nbd)^2+n(ad+bc)^2$
このままじゃ上手くいかないので少し変形させる。$a→\sqrt{m}a,d→\sqrt{m}d$と変数変換すると
$(ma^2+nb^2)(c^2+mnd^2)=m(ac-nbd)^2+n(mad+bc)^2$
$m=k-1,n=-k,a=x,b=y$とすると
$((k-1)x^2-ky^2)(c^2-k(k-1)d^2)=(k-1)(xc+kyd)^2-k((k-1)xd+yc)^2$
$ c^2-k(k-1)d^2=1$となるように$c,d$を取りたいが$(c,d)=(2k-1,2)$とすれば良い。そうすることで補題の恒等式を得た。

$(ii)$の$ \Longrightarrow $の発想

$k,a$の具体例を考えてみる。
$ X_{2,14}=\{(2,3),(6,5),(18,13),(38,27),(106,75)\cdots\}$
補題の恒等式から特に$k=2$として
$(x_{n+1},y_{n+1})=(|3x_n-4y_n|,|2x_n-3y_n|)$という数列を考えてみる。例えば$(x_1,y_1)=(106,75)$としたら
$(x_2,y_2)=(18,13)$
$(x_3,y_3)=(2,3)$その後は$(2,3),(6,5)$が交互にループする。この数列は$(x_1,y_1)\in X_{2,14}$としたら$x_n,y_n$が単調減少して十分先で$(2,3),(6,5)$がループする…？
一般化すると$(x_1,y_1) \in X_{k,a}$
$(x_{n+1},y_{n+1})=(|(2k-1)x_n-2ky_n|,|(2k-2)x_n-(2k-1)y_n|)$
としたら$x_n,y_n$が単調減少して十分先でループする…？
単調減少であることが示せないかと考えたら$ x_n>y_n$なら$ x_{n+1}< x_n,y_{n+1}< y_n$であることが示せた。だから$x_t< y_t$となる$t$が存在しないと$x_n,y_n$は十分小さく取れるけど$x_n,y_n$は非負整数だから矛盾。だから$ x_t< y_t$となる$t$が存在する。これは無限降下法やvieta jumpingと似た論理だ。上の証明では最小値を取る方法をしているが本質的に差はない。

まとめ

vieta jumpingと似た論理を使う良問でした。