数オリのテクニック〜Vieta jumping〜

Vieta jumping

Vieta jumping とは,ある文字について二次式であるような不定方程式を,解と係数の関係を用いて解くテクニックです。

数学オリンピックの不定方程式の中でも難し目の問題に使えるテクニックです。

Vieta jumping の手順

手順1:ある文字について二次の不定方程式に変形する。そのときに二次の係数が1で,一次の項と定数項が整数となるならVieta jumping が使えるかもしれない。

手順2: 解が存在するなら,解と係数の関係よりもう一組別の解が作れる。それらを使って解の条件を絞る,または解が存在しないことを導く。

手順1はたいてい簡単ですが,手順2はけっこう難しいです。

数オリの問題に挑戦

国際数学オリンピック1988オーストラリア大会第6問です。当時はVieta jumpingが知られていなかったため20世紀で二番目に平均点の低い問題となっています。

問題

ab+1ab+1a2+b2a^2+b^2 を割り切るような正の整数 a,ba,\:b に対して,a2+b2ab+1\dfrac{a^2+b^2}{ab+1} が平方数であることを証明せよ。

方針

今回は手順1は簡単です。手順2では「最小性に矛盾させる背理法」で証明します(これは Vieta jumping の手順2でよく使う方法)。

解答

a=ba=b の場合は a2+b2ab+1\dfrac{a^2+b^2}{ab+1} が整数となるのは a=b=1a=b=1 の場合のみで,その値は 11 となり主張は正しい.よって,以下 aba\neq b で考える.平方数でない nn を固定して不定方程式 a2+b2=n(ab+1)a^2+b^2=n(ab+1)\: (ただし a,  b,na,\;b,\:n は正の整数で aba\neq b)が解を持たないことを証明すればよい。

不定方程式の対称性より変数を交換しても解となるので (a,b)(a,b) が解なら (b,a)(b,a) も解.よって,もし aba\neq b なる解が存在するなら a>ba > b なる解が存在する。したがって,a>ba > b なる解が存在すると仮定して矛盾を証明すれば aba\neq b なる解の存在が否定される。

よって,解 (a,b)(a,b) が存在すると仮定すると,解はいくつかあるかもしれないが, a>ba > b なる解 (a,b)(a,b) の中で aa が最小であるようなもの(※)を持ってこれる。これを (a0,b0)(a_0,b_0) とおく。(a0,b0)(a_0,b_0) が不定方程式を満たすなら,a0a_0

x2nb0x+b02n=0x^2-nb_0x+b_0^2-n=0

の解である.よって,解と係数の関係より c0=nb0a0c_0=nb_0-a_0 とおくと,c0c_0 もこの二次方程式の解である。よって,(c0,b0)(c_0,b_0) ももとの不定方程式の解である.そして,c0c_0 は整数である.また,不定方程式の対称性より (b0,c0)(b_0,c_0) も解である。

あとは,b0>c0b_0 > c_0 かつ c0>0c_0 > 0 を証明すれば, (b0,c0)(b_0,c_0) という解の存在により a0a_0 の最小性(上記の※)に矛盾するので目標の主張が証明される。

  • b0>c0b_0 > c_0 について. a0c0=b02na_0c_0=b_0^2-n より a0c0<b02a_0c_0 <b_0^2 .これと a0>b0a_0 > b_0 より b0>c0b_0 > c_0
  • c0>0c_0 > 0 について. c0=0c_0=0 と仮定すると,b02=nb_0^2=n となり nn が平方数でないことに矛盾. c0<0c_0 <0 と仮定すると,不定方程式の左辺:c02nb0c0+b02nc02+n+b02n>0c_0^2-nb_0c_0+b_0^2-n \geq c_0^2+n+b_0^2-n > 0 となり (b0,c0)(b_0,c_0) が解であることに矛盾。

Vieta jumping に関して

  • 二次の不定方程式に帰着できたら Vieta jumping を使う前に「判別式が平方数」という条件から範囲を絞れないか確認するべきです。Vieta jumping は判別式が通用しないときに初めて発動するテクニックです。
  • 上記の問題は Vieta jumping を使う問題の中では自分の知っている限り最も易しい問題です。それでも手順2がけっこう険しいです。この手の問題は「Vieta jumping というテクニックを知らないと無理,知っていても簡単ではない」という手強いものになっています。
  • Vieta jumping を使う多くの問題では,手順2で「何かしらで最小な解の組を持ってくる→解と係数の関係から別の解がつくれる→最小性に矛盾→だから解は(ある条件のもとで)存在しない」という手段を使います。また,不定方程式の対称性を使って別の解を作る(上記の例では bbcc を交換する)ことも頻出です。
  • ちなみに,解と係数の関係のことを英語でVieta’s formulaといいます。

参考文献: The Method of Vieta Jumping(英語です)

空までjumping~

Tag:国際数学オリンピックの過去問

Tag:不定方程式の解き方6パターン