ISL 2016 N5 証明と発想

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

証明

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

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

$(ii)$の$⟸$の証明

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

$(ii)$の$⟹$の証明

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

発想

補題の恒等式の発想

まず分母払って整理したら$(k-1)x^2-k{y}^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+n{b}^2)(c^2+n{d}^2)=(ac-nbd{)}^2+n(ad+bc{)}^2$
このままじゃ上手くいかないので少し変形させる。$a\to \sqrt{m}a,d\to \sqrt{m}d$と変数変換すると
$(m{a}^2+n{b}^2)(c^2+mn{d}^2)=m(ac-nbd{)}^2+n(mad+bc{)}^2$
$m=k-1,n=-k,a=x,b=y$とすると
$((k-1)x^2-k{y}^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)$の$⟹$の発想

$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-2k{y}_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と似た論理を使う良問でした。