二次式として表される不定方程式, 特にVieta Jumpingについて解説を行います.
まずは判別式を見よう
本題に入る前に, より根本的な手法について抑えておきましょう. 基本となるのは以下の事実です.
最も基本的な問題を考えましょう. 以下の不定方程式を整数範囲で解いてみます.
上の式ほど露骨ならば気付きやすいですが, 実際にはもう少しわかりにくい形に隠してあることが多いです. どの文字も三次以上であるものの, 適切な置換を行えば二次に落ちる文字が現れるパターンもあります. とはいえ少なくとも, 二次の文字が始めから存在するときは, まず判別式を念頭に置くようにしましょう. Vieta Jumpingは, それをしてからです.
以下をみたすような整数の組
移項すると実は因数分解できます. すると
求める解
与式は以下のように整理できる. 特に以下
以下をみたすような正の整数の組
このまま展開すると
求める解は
ここで元の方程式を解くと, 正の整数解
余談. もし題意が単に整数解であれば, 任意の整数
以下をみたすような正の整数の組
上問と発想は全く同様です. 右辺の分数式が明らかに鬱陶しいので…?
Vieta Jumping
Vieta Jumpingとは整数論において, 二次方程式の解と係数の関係を用いたテクニックです. 別名をRoot Flippingとも言います. 1988年のIMOオーストラリア大会の問6での出題が初出であるとされています. この問題は西ドイツによって提出され, あまりの難しさに出題を躊躇う空気もあったようですが, 実際のコンテストでは11名が見事に完答しました. とはいえ, 結局これは20世紀のIMOで二番目に平均点の低い問題となりました.
しかしこれをきっかけにVieta Jumpingはすっかり定着しました. いわゆる「マスターデーモン」をきっかけにLTEの補題が定着した流れのようです. 20年の時を経てIMOベトナム大会で再び姿を現した時には, もう2番級になっていました.
最大のポイントは「解の存在を仮定すれば, 解と係数の関係から別の解が作れる」ということです. これを用いて解の条件を縛ったり, 矛盾を導いたりします. とはいえこれだけでは良くわからないでしょうし, 一から自己開発するのはやや困難な部類の議論だと思うので, 初見の人はとりあえず実例を見てしまっても良いと思います.
近年では安直にそのままな出題はほとんど見られなくなってきましたが, とはいえ類似の発想を肝とする問題はSLPを中心にまだまだ健在です. これを機にマスターしてしまいましょう!
任意の実数
まず解を見つけましょう. そこから
自明な解
商
商となりうる正の整数
ここで以下の
問5のように
商となりうる正の整数
ここで以下の
まずは
以下の変形より,
条件をみたす組
ここで以下の
これまでと同様に
商となり得る正の整数
ここで以下の
公式PDFに掲載のSolution 3を参照してください. (著者の気分次第で和訳される可能性があります)