Aggressive Style 5

読者です 読者をやめる 読者になる 読者になる

Aggressive Style 5

昨今はコミケ関係を中心に書いています。同人やニコニコ動画方面で活躍される方の相互リンクをお待ちしています。

【質問の解答】xyの項のある放物線(x^2+xy+y^2/4^2y=0)の自然数解が無数に有る事を示す

今日は以前書いた記事(2)が難しい問題(2010 名古屋大学理系 大問4)の質問が来たので、喜んで回答したい。

質問

x^2+x y+y^2/4-2 y=0(放物線) 上の格子点をすべて求めていただけませんか。お願いします

問題

放物線 x^2+xy+\frac{y^2}{4}-2y=0上の格子点をすべて求めよ。

C言語で確認

ひょっとしたら名古屋大学の問題同様格子点が無数個あるかな?と踏んだので、まずC言語で格子点が無数あるかどうか調べてみた。ここで題意を読み替えさせてもらって、

放物線x^2+xy+\frac{y^2}{4}-2y=0が格子点をもつ
<=> 2元2次形式のディオファントス方程式(不定方程式) x^2+xy+\frac{y^2}{4}-2y=0 が整数解(x,y)をもつ

と考えて行く。さて方程式の解を求めるとは、「(左辺)=(右辺)となる(x,y)(の集合を)求める」事であった。そこで左辺に適当な値を代入しつづけ、しらみつぶしに(x,y)を探す事をしたい。以下、この作業をC言語に丸投げしてみた。

探索範囲

-100\leq x \leq 100 -100\leq y \leq 100

プログラム

結果(整理)

(-63,98),(-48,72),(-35,50),(-35,98),(-24,32),(-24,72),(-15,18),(-15,50),(-8,8) ,(-8,32),(-3,2),(-3,18),(0,0),(0,8),(1,2)の15個

この事からどうも答えが無限に有りそうな予感がする。そこで問題を以下のように切り替えて回答したい。

議題変更

放物線x^2+xy+\frac{y^2}{4}-2y=0上の格子点は無数に存在するか?

解説

ディオファントス方程式の整数解を求めるのもCase by Caseである。これといった方法が無いからこそ毎回毎回受験生の頭を悩ませ続けていた。困った事に「ヒルベルトの第十問題」より数学的にもその方法が無い事が示されているようだ。

整数係数の方程式f(x_1,x_2,....,x_n)=0が整数解を持つか否かを有限的に判定する方法は存在しない*1

しかしながら2元以上の2次形式(2次方程式)のディオファントス方程式の場合ならば、多くの場合xかyかに整理して判別式の値D=m^2と、判別式が平方数かどうか探して行く事が多い。

答え

問題の式を整理し、x^2+{(y-2)x}+\frac{y^2}{4}=0。これをxについて解くと、 x= \frac{(-y) \pm \sqrt{8y}}{2}

このときxが整数解を持つ為にはDが平方数であることが必要。ここで(\forall{m}\in Z)とし、y=2m^2のときD=4mx=-m^2+2m,-m^2-2mとmが1つ定まれば整数yが1つ定まり、それに対し整数xが2つ定まる。ここで全てのmに対し上記が成立するので、方程式の整数解(x,y)は無数に存在する q.e.d

その他

学年が分からないから推測で書くけど、リンク先から来てるあたり、下の図のように恐らく放物線を回転移動と平行移動(アフィン変換とも言う)してax^2+bxの形にして(写像して)、名古屋大学の問題より...とやりたかった気もする。

f:id:RyuichiXP:20160929020425p:plain

問題の様子が分からなかったから、とりあえず約40,401=(201*201)通り総当たりで調べさせた。こんな風にプログラムなどの処理の手順等の事をアルゴリズムなんて言うけど、整数自体はプログラムのアルゴリズムなんかでも頻出のテーマ。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

要は入試でこんな問題を出す理由は、「アルゴリズム(手順)の説明が出来るか否か?理由を具体的に説明できるか?」を見ていたり。中学入試、高校入試、大学入試問わず上位校になればなるほどこの辺は見て来る物なので注意の事。

類題

東大理科 2006前期(第4問)

参考にした文献