2014/10/22

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

分野: 整数問題  レベル: 数学オリンピック

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

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

Vieta jumpingの手順

手順1:ある文字について二次の不定方程式に変形する。そのときに二次の係数が1で,一次の項,定数項が整数となるならVieta jumping が使えるかもしれない。
手順2:解が存在するなら,解と係数の関係よりもう一組別の解が作れる。それらを使って解の条件を絞る,または解が存在しないことを導く。

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

数オリの問題に挑戦

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

問題

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

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

解答

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

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

よって,解$(a,b)$ が存在すると仮定すると,解はいくつかあるかもしれないが, $a > b$ なる解$(a,b)$ の中で $a$ が最小であるようなもの(※)を持ってこれる。これを$(a_0,b_0)$ とおく。$(a_0,b_0)$ が不定方程式を満たすなら,$a_0$ は $x^2-nb_0x+b_0^2-n=0$
の解である.よって,解と係数の関係より $c_0=nb_0-a_0$ とおくと,$(c_0,b_0)$ も解である.そして,$c_0$ は整数である.また,不定方程式の対称性より$(b_0,c_0)$ も解である。

あとは,$b_0 > c_0$ かつ $c_0 > 0$ を証明すれば,$(b_0,c_0)$ という解の存在により $a_0$ の最小性(上記の※)に矛盾するので題意は証明される。

  • $b_0 > c_0$ について. $a_0c_0=b_0^2-n$ より $a_0c_0 <b_0^2$ .これと $a_0 > b_0$ より $b_0 > c_0$ 。
  • $c_0 > 0$ について. $c_0=0$ と仮定すると,$b_0^2=n$ となり $n$ が平方数でないことに矛盾. $c_0 <0$ と仮定すると,不定方程式の左辺:$c_0^2-nb_0c_0+b_0^2-n \geq c_0^2+n+b_0^2-n > 0$ となり$(b_0,c_0)$ が解であることに矛盾。

Vieta jumpingに関して

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

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

空までjumping~

Tag: 国際数学オリンピックの過去問
Tag: 不定方程式の解き方6パターン

分野: 整数問題  レベル: 数学オリンピック