数学オリンピック史上最高難度 Vieta Jumpingで解く

[@ヌートリア-b1k]

思い出深い問題です、高校時代友人に誕生日プレゼントとして出された問題がこれでした。整数問題は得意な方で数オリの本戦の問題でも解くことができるぐらいだったのですが、この問題に関しては一ヶ月かけても解くことができなかったのを覚えています。解説を見てvieta jumpingを初めて知り、自分の未熟さを思い知ったのと同時にすごく感動した思い出があります。

[@マルチーズ先生のやさしい東大数]

思い出話を有難うございます。感銘しました！

[@user-catBrathers]

平方数よりも平方数じゃないことを表現する方が難しいのに、あえて「平方数じゃないと仮定して降下法」で証明するのが、トリッキーな気がする

[@マルチーズ先生のやさしい東大数]

確かにそうですね。

[@ゆう_yuitrob]

平方数じゃないことが効果的に効いてるはずなのに証明中目立たない感じにヌルッと出てくるからビビる

[@ファースト-o1d]

数オリ解説する方少ないので有難いです！ もっと解説してくれると非常に嬉しい…！

[@マルチーズ先生のやさしい東大数]

有難うございます。面白そうな問題があれば、アップしたいと思います。

[@marimo_123]

解法自体はとてもすっきりしているのがポイント高いですね

[@マルチーズ先生のやさしい東大数]

有難うございます！

[@jj-jg7dl]

平方数になることの証明っていう一見行けそうな感じだから平方数にならないと仮定するのはクソ難しいな

[@マルチーズ先生のやさしい東大数]

思いつくのが難しいですよね。。。

[@miya-w2o]

1つ1つやってることは整数問題と背理法なので中3か高1くらいの内容なんだけど、自力で解け言われたら無理やな．．． 面白い良い問題だわ

[@マルチーズ先生のやさしい東大数]

そうなんですよね。思いつくことが大変です。

[@カーネル-j3o]

もう凄すぎて感動しちゃいました。こんな綺麗な編集の動画ありがとうございます。

[@マルチーズ先生のやさしい東大数]

このようなコメントをもらえると感動します！

[@vorsokratiker4420]

解と係数の関係で矛盾が出せるかもと気が付けば解けるんでしょうね。 大学入試でも誘導付きなら普通に出そうな感じがしますね。 数学オリンピックの難問って、解と係数の関係をアクロバティックに使わせるの好きですよね。それだけ重要な性質ということなんでしょうけどね。

[@マルチーズ先生のやさしい東大数]

思いつくかがカギですね。

[@Satou_Takashi]

最初は a,b={1,1}の場合のみa²+b²がab+1の倍数になるのではと予想したけど、その予想は見事に外れた。 プログラムで検証しか結果、まずb=a³の場合、(a²+b²)/(ab+1)=a²が常に成立することが分かりました。 さらに{8,30}、{27,240}、{30,112}など、いくつかの他の解も見つけましたので完全にお手上げです。

[@マルチーズ先生のやさしい東大数]

b=a^3の時のみ成立すると思ってましたが、他に解があったのですね！有難うございます。

[@JunyaS.]

@@キャットマウス いや、有限個しか解が存在しないなら、 「有限個しか解が存在せず、その全てで題意を満たす」 ということを証明すれば良いし、また、解は無限個存在するけどそれに対応する(a,b)に法則性があるなら、 「(a,b)がこのような法則性を満たしている時のみ題意を満たし、またそれ以外では題意を満たさない」 ということを証明すれば良いので、一般に(a^2+b^2)/(ab+1)が整数になる場合について証明するより簡単な可能性がありますよね？ だけど解は無限個ある上に法則性もいまいちよく分からなかった、って事でしょ

[@jalmar40298]

この動画の証明を精査すればわかるんですが、平方数kを固定したとき、解の組を一つ見つければそれより大きい解の組を得られます k=n^2(≧4)とし、(A,B)をA

[@マルチーズ先生のやさしい東大数]

@@jalmar40298 すばらしいコメント有難うございます。この問題をコンプリートできた気持ちになりました！

[@サトウ-f2s]

​@@JunyaS. 解が無限個あるかどうかは言及してないけど、規則性がわからないからお手上げだと、コメント読んだら分かるよ、わざわざ言い直す必要ない

[@uxan9598]

高校時代に無限降下法を初めて見た時、なんだこの証明法は！？って衝撃を受けたけど、ビエータジャンピングはその比じゃないくらい衝撃

[@マルチーズ先生のやさしい東大数]

有難うございます！

[@anasuit1111]

自然数x,y,zを用いて(x^2＋y^2＋z^2)/xyzとかける自然数を求めよという問題で悩んでいたとき、ふとvieta jumping を用いたらうまくいくかなと閃いて無事解けたのを思い出した

[@マルチーズ先生のやさしい東大数]

2006年の東大入試と似てますね。

[@sterben253]

@anasuit1111さん よければその問題の出典か解説を教えて欲しいです。 小一時間考えたのですがうまく最小解が見つけられませんでした。

[@anasuit1111]

@@sterben253 自分の解答を載せておきますね (以下解答) まず正整数kを用いて(x^2＋y^2＋z^2)/xyz＝kとおく。kを固定させ、与式を満たす(x,y,z)の集合をSとすれば、この元のうちx＋y＋zが最小のものが存在するから、そのうちの１つを(X,Y,Z)とする。このとき一般性を失わないからX≧Y≧Z≧1•••①としてもよい。以下 X^2≦Y^2＋Z^2であることをjumpingにより示そう。 仮にX^2＞Y^2＋Z^2とする。ここでtの2次方程式 t^2-kYZt＋Y^2＋Z^2＝0 を考えるとt＝Xは解の１つ。他方の解をt＝X’とすれば解と係数の関係より以下が従い、X’も正整数である。 X’＝kYZ-X＝(Y^2＋Z^2)/X これより(X’,Y,Z)∈Sだが仮定より X’＝(Y^2＋Z^2)/X＜X となるからXの最小性に矛盾する。 これより X^2≦Y^2＋Z^2•••② がいえる。さて、①と②より k＝(X^2＋Y^2＋Z^2)/XYZ ≦2(Y^2＋Z^2)/XYZ ≦2(Y^2＋Z^2)/Y^2Z ＝2(1/Z＋Z/Y^2) ＜2(1＋1)＝4 (最後の評価はY＝Z＝1、即ちX＝Y＝Z＝1のとき成立するもので、この場合k＝3であるため等号は省略した) ∴1≦k≦3•••③ 次にそれぞれのkで十分性を満たすかどうかを検討する。 (1)k＝1のとき x＝y＝z＝3とすればよい。 (2)k＝3のとき x＝y＝z＝1とすればよい。 (3)k＝2のとき このような(x,y,z)が存在しないことを示そう。 x^2＋y^2＋z^2＝2xyz•••③ において左辺は2で割り切れるから(x,y,z)のうち2つは奇数で１つが偶数、全て偶数の場合が考えられ、前者は4を法とすることで (左辺)≡2、(右辺)≡0となるため不適。よってx,y,zは全て2で割り切れる。x＝2x’、y＝2y’、z＝2z’(x’、y’、z’は全て正整数)とおくと、③に代入して (x’)^2＋(y’)^2＋(z’)^2＝4x’y’z’ 従って(x’、y’、z’)もさらに2で割り切れる。同様の操作を繰り返すことでx,y,zは2で無限回割り切れることになるため不適。 以上より求める答えは1、3

[@sterben253]

@anasuit1111さん何度もすみません。 vieta jumpingについてz=1の時は簡単にこのテクニックがつかえて有名なのは知っているのですが、一般のzについてこれが言えるかはかなり厳しいのではないかと思います。 出典についても色々と調べましたがこれに該当するものは見つけられませんでした。 これを見ている方でこの問題の解法を知っている方はぜひ教えてください🙇‍♀

[@anasuit1111]

@@sterben253 昨日書いたはずだけど消えてるようだからまた載せますね ヒントとしては ①1≦x≦y≦zとしたときx^2＋y^2≧z^_2であることをjumpingを用いて示す。 ②①を使って、問題の式が取りうる値を絞る ③その値一つ一つを吟味する って感じです

[@nakahama7776]

整数は自信あったから数時間頑張ったけど無理だった。この方法を知れて感動した。

[@マルチーズ先生のやさしい東大数]

有難うございます。お役に立てて良かったです！

[@圃匙琥逗]

Vieta jumpingを用いた解法を見て常々思っていることは、題意の命題 ∀(a, b) ∈ N^2, P(a, b)（今回で言えば, P(a, b) : 「(ab + 1) | (a^2 + b^2) ならば (a^2 + b^2) / (ab + 1) は平方数」）の否定 ∃(α, β) ∈ N^2; ¬P(α, β) に対して集合 S := {a+b | ¬P(a, b)} は自然数の集合 N の空でない部分集合（背理法の仮定から α+β ∈ S より非空）であって, N が整列集合だから S は最小元 A+B を持つって事実を暗黙に使用してるよね。

[@ああ-b6i7s]

そうですね。何にせよ、集合の言葉を一度知ると本当便利で思考の手助けになってくれますね

[@MultiYUUHI]

題意は(a^2+b^2)=c(ab+1)となる整数cがある事。 aの二次方程式と見て、 a^2-bca+b^2-c=0 解の公式を用いる。ルートの中身をDとおく。 D=(bc)^2-4b^2+4c=N^2 とならなければ√がはずれない。 (bc-N)(bc+N)=4(b-√c)(b+√c) bc-Nとbc+Nは共に偶数 [(bc-N)/2][(bc+N)/2]= (b-√c)×(b+√c) 左辺は整数の積で共に1となることはないから 右辺は2以上の整数の積で因数分解される、これが実現するcは 平方数である。 平方数であ

[@ワキガンテ]

bc-Nとbc+Nが共に偶数と言えるのは何故ですか？

[@山-l5i]

bc-Nが偶数であるということは bcとNの偶奇が一致するということで、bc+Nも偶数であると考えられると思います

[@anasuit1111]

b±√cって必ずしも整数とは限らないんじゃ？

[@山-l5i]

⁠@@anasuit1111確かにそうですね、その場合は一意性が無いので積の形で進めていけませんか？難しいですね

[@cp-fvhjk]

最後の部分は b^2-cとなり任意の整数cで整数となることは分かっており、整数は素因数分解できるので、cが必ずしも平方数とはいえませんね。

[@hachihuit88]

解説聞けば私でも理解できるような問題なのに、著名な数学者が何人も集まっても解くことができないのか。いやはや、数学は奥が深いねぇ。

[@マルチーズ先生のやさしい東大数]

シンプルで難しいものが、本当に難しい。含蓄があります。

[@koji0527kk]

難しいですね。 とっかかりが分からず、手も足も出ませんでした。

[@マルチーズ先生のやさしい東大数]

初めに解法を確立した人が凄いですよね。

[@すわわわわわ]

有限群論とかでも見たことある証明方法ですね。条件を満たす最小の位数の群があると仮定して、それより小さい群があることを示すという論法。誘導も何もなしで見つけるのはそら無理でしょうｗ

[@マルチーズ先生のやさしい東大数]

専門的なコメント有難うございます！

[@antama9488]

解説を聞いても解けるようになる気がしない

[@マルチーズ先生のやさしい東大数]

使うべき場面の見極めが難しそうですね。

[@nanilnull]

kが平方数ならx>=0、平方数でないならx>0。この差だけから「x>0での最小仮定に反する」って言うの、いくら何でも的が小さすぎる。数オリだとそのレベルなのかな？

[@うっちゃん-e8e]

条件よりa^2₊b^2₌p(ab₊1)(但しpは正の整数)とおける。 　展開してaで整理するとa^2₋pba₊b^2₋p₌0　　　① 　aの実数条件より判別式をとると(pb)^2≧4(b^2₋P)　　② (1)p≦2のとき 　②式より(4₋p^2)b^2≦4p　1≦b^2≦4p/(4₋p^2)より条件式を満たすpはp₌1のみ。 　p₌1より1≦b^2≦4/3と自然数bの条件からb₌1、よってp₌b₌1で①式よりa₌1 　(a^2₊b^2)/(ab₊1)₌1となる。 (2)p>3のとき 　②式は常に成立するので①式のaはa₌{pb±((pb)^2₋4b^2₊4p)^1/2}/2　　　③ 　aは自然数より③式の√　内は平方数になる必要があるので 　(pb)^2₋4b^2₊4p₌k^2(kは正の整数)とおく。　　(pb)^2₊4P₋4b^2₋k^2₌0　　④ 　④式をpについて解くとp₌{₋2₊(4₊4b^4₊(bk)^2)}/b^2　　　⑤ 　Pは正の整数より⑤式の√　内は平方数となるので、4₊4b^4₊(kb)^2₌t^2とおく。　　⑥ 　⑥式を変形してt^2₋4₌b^2(4b^2₊k^2)　　　⑦ 　⑤式が正整数よりt≧3が必要で⑥式からt^2₋4₌(t₊2)(t₋2)₌4b^4₊(kb)^2₌b^2(4b^2₊k^2)　　⑧ 　k、bは正の整数より4b^2₊k^2>b^2となるのでt₊2₌4b^2₊k^2　⑨　t₋2₌b^2　　⑩ 　⑨₋⑩より4₌3b^2₊k^2　⑫　⑫式が成り立つ場合b₌k₌1となりこのときt₌3 　従って⑤式に代入しP₌1となる。このとき③式よりa₌1となる 　以上より(a^2₊b^2)/(ab₊1)₌1が成り立つ。

[@マルチーズ先生のやさしい東大数]

熱意のあるコメント有難うございます！

[@user-shiny_doublade]

(1)でp=2の場合を無意識に省いてしまっているようなので、そこは別に計算する必要がありますね。 途中まではいい感じなのですが、⑧から⑨が成り立たないです。b=2，k=8，t=16などを代入するとわかりやすいですが、合成数を2つの因数に分解する方法は複数通りあり、今回の問題ではこの手法で解くのは難しそうです。無論、t^2が素数やその累乗で表されるときなどには、この手法は有効です。

[@うっちゃん-e8e]

ご意見いただきまして有難うございました。 ただ⑦式まで問題ないとして⑦にb₌2、k₌8、t₌16を代入しても成立しないので私には理解できません でしたが、ただ(2)はp＞3のときを前提にしているので、この解答では成立しないことになります。 言われるように因数に分解する方法は複数ありますので、わかる範囲でやってみました。 前提条件としてt、b、kは整数とします。 1)　t₊2₌b(4b^2₊k^2)　①　t₋2₌b　②　のとき 　　①₋②より４₌4b^3₊(k^2₋1)b　このときb₌1、k₌1となりt₌3、p₌1となり不成立 2)　t₊2₌b^2(4b^2₊k^2)　③　t₋2₌1　④のとき 　　①₋②より4₌4b^4₊(kb)^2₋1より5₌b^2(4b^2₊k^2)　この場合もb₌1、k₌1となり不成立 　以上よりp＞3のときは成立するa、b、pは存在しないことになります。 　この方法ではまだ不十分かもしれませんが、私の解答では、p₌1でa₌1、b₌1のときのみ成立 　することになりました。 　もしa、bが1以外で成立する場合をご存じであれば教えていただきたいと思います。

[@user-shiny_doublade]

@@うっちゃん-e8e 返信ありがとうございます。ご指摘の通り、私の挙げた例は不適切でした。正しくは t=18です。申し訳ないです。 このとき t^2-4=18^2-4=320 b^2(4b^2+k^2)=2^2(4×2^2+8^2) =4×80=320 となり、条件を満たすことがわかると思います。 これを因数分解の形で無理やり示すなら t+2=b^2+(k^2/4) , t-2=4b^2 でしょうか？ kが偶数であるため、k^2/4は整数になります。 (a,b)=(1,1)以外にも条件を満たすものがいくつかあるため、下に示します。 ① (a,b)=(n^3,n)のとき (a^2+b^2)/(ab+1) =(n^6+n^2)/(n^4+1) =n^2 私が上で挙げたものはn=2、つまり(a,b)=(8,2)の例。 (8^2+2^2)/(8×2+1)=68/17=4 ② (a,b)=(n^5-n,n^3)のとき (a^2+b^2)/(ab+1) =(n^10-2n^6+n^2+n^6)/(n^8-n^4+1) =n^2 n=2なら (30^2+8^2)/(30×8+1)=964/241=4 他質問等ありましたら、是非お願いします。

[@うっちゃん-e8e]

丁寧な解説いただきまして有難うございました。

[@test-sh1yt]

なるほど、いくらでも小さな解を生成できちゃうのが矛盾点なのね

[@マルチーズ先生のやさしい東大数]

無限降下法ですかね。

[@男磨きをします]

説明聞けばそこまで難しいことはしてないけど、思いつくの無理すぎる

[@マルチーズ先生のやさしい東大数]

何事も、最初に考えた人は偉いですね！

[@ularaippanjin1484]

(a^2+b^2)/(ab+1)=k を変形してなんとか平方数に持っていけないかと思ってたら解法それか

[@kumamonslayer]

ぱっと見難問なのに、答え自体は中学生とかでも理解できるのすげー

[@マルチーズ先生のやさしい東大数]

そうですね！

[@とある京都の劣等生]

無限降下法みたいな感じか

[@マルチーズ先生のやさしい東大数]

はい。「解と係数の関係」＋「無限降下法」ですね。

[@tonaiSE]

背理法の究極版って感じですね。。。

[@マルチーズ先生のやさしい東大数]

「解と係数の関係」＋「無限降下法」という感じでしょうか。

[@山田たか-y8s]

ab+1で割り切れるという条件が活用できているのか、他の条件ab+2などでもできてしまうのでは？という疑問を感じつつよくわからなかったのでまた明日見に来ます

[@男磨きをします]

最初にあの分数式を自然数kとおいている時点で、割り切れるという条件を使っています

[@マルチーズ先生のやさしい東大数]

@@男磨きをします コメント有難うございます。その通りです。

[@桜金プラ]

解の組み合わせとして、[n, n^3], [n^3, n(n^4-1)] を見つけたけど、それ以外にあるでしょうか。

[@マルチーズ先生のやさしい東大数]

すばらしい！

[@chamakebin1023]

[n(n^4 - 1), n^3(n^4 - 2)]

[@マルチーズ先生のやさしい東大数]

@@chamakebin1023 すごい。どんどん出てきますね！

[@りっこ70.1]

むつかしい

[@itohru]

なるほどな これはスッキリ

[@マルチーズ先生のやさしい東大数]

有難うございます！

[@JunyaS.]

はえー無限降下法って有能なんやな

[@マルチーズ先生のやさしい東大数]

そうですね。ちょっと不思議な感じがしますが、証明問題に有能ですね！

[@sgrjoachim4046]

／(^o^)＼ﾜｶﾗﾝ

[@マルチーズ先生のやさしい東大数]

説明が拙く、スミマセン。。。

[@田村博志-z8y]

最小解とは何の数値に注目して最小と言ってるのかわかりません。 a + b ?

[@マルチーズ先生のやさしい東大数]

はい、通常は、a+bが最小になる場合です。例外があるかは、私も研究不足ではっきりとしたことは言えません。。。

[@totonanode]

これみるたび思うけど、主張すごいよな.成り立ちそうにも一見見えないしvieta知らないとまず無理そうだし...

[@マルチーズ先生のやさしい東大数]

問題を考えた人、凄いですね！

[@p0utan]

あのTerence Taoが解けなかったと言う問題 私も結構考えたが解けませんでした笑

[@マルチーズ先生のやさしい東大数]

Terence Taoが解けなかったのですね。びっくり！

[@wswsan]

仮定して矛盾点を出すの, 背理法みたい

[@マルチーズ先生のやさしい東大数]

その通りです。

[@猿田彦-s9o]

京大数学にも似たような過去問があったような気がするw 流石にここまで難しくはなかったけど

[@マルチーズ先生のやさしい東大数]

そうなんですね。

[@光蜂こうはち]

これは流石に一度答えを見ないと一生辿り着ける気がしない…

[@マルチーズ先生のやさしい東大数]

そうですね。。。

[@白猫で煽る弁護士]

こんな難しい問題、どうやって作問しているんた…？

[@マルチーズ先生のやさしい東大数]

聞いてみたいですね。。。

[@jalmar40298]

vieta jump って何がジャンプなの？

[@マルチーズ先生のやさしい東大数]

vietaは、解と係数の関係を表します。最小解を設定したあと、vietaによって、さらに小さい解が得られるところを、jumpingと言っているのだと思います。

[@jalmar40298]

@@マルチーズ先生のやさしい東大数 なるほどね

[@たいき-r8v]

はぁ… 追いつけないねぇ おもろい

[@マルチーズ先生のやさしい東大数]

シンプルで面白いですよね。

[@簡単金剛]

言いたいことはわかるけど 高校生にこれ、、？

[@マルチーズ先生のやさしい東大数]

確かに難しすぎますよね。。。

[@CH-xd5zk]

やばすぎる これやばい やば

[@マルチーズ先生のやさしい東大数]

やばいです！

[@あき-s1u1q]

よく分からんが凄い

[@マルチーズ先生のやさしい東大数]

有難うございます！

[@人間とハダカデバネズミのキメラ]

問題作成委員会の人が解けないのになんで答えあるんだ？全員解けないわけではないのか

[@マルチーズ先生のやさしい東大数]

スミマセン、説明を省いたのですが、数学オリンピックで解けた人が11名いたようです。おそらく、その方々の解法を整理して1つのテクニックにしたのだと想像します。

[@りるうく]

@@マルチーズ先生のやさしい東大数 横からすみません。問題作成委員会の人が証明できてないなら、この主張が正しいかどうか分からず、問題として出せないはずじゃないかな？と思いました。正しいなら証明、正しくないなら反例を示せ、という問題形式なら成り立ちますが・・・・。

[@マルチーズ先生のやさしい東大数]

@@りるうく 私も不思議に思いました。だから最後の問題として出したのですかね。。。

[@p0utan]

作った人は作為があるので解がわかっているということかな 作者以外の委員会メンバーが解けなかったのではないか

[@マルチーズ先生のやさしい東大数]

@@p0utan はい、私のそのように想像してます。

[@hiromori3960]

「AならばBである」この命題の待遇は「BでないのならばAではない」・・・提示された命題を証明したければ、その命題の待遇を証明する。数学論理の基本なのですが、これは「大学入試数学難問あるある」の「にっちもさっちも行かなくなったら、背理法を使え」というヤツです。「因数と式」の問題のように見えて、本質的には「命題と集合・論理」を理解しているかが重要。ところで、論破で有名なひろゆきにセンター数学過去問「命題と集合・論理」の設問を１０年分ぐらいやらせてみたら、果たして彼は満点が取れるのでしょうか。

[@マルチーズ先生のやさしい東大数]

面白いコメント有難うございます！

[@hyujack]

そんなのってありかよ...

[@next7743]

オーストラリア問題作成委員会ちょっとこい

[@有名になりたけりゃ俺に従え]

解けないなら出すなよ...

[@マルチーズ先生のやさしい東大数]

優秀な受験生に解かせようとしたんですかね。。。

[@この顔にピンときたら-g8l]

無限降下法的な？

[@マルチーズ先生のやさしい東大数]

はい、「無限降下法」と「解と係数の関係」のハイブリッドですね。

[@syokup]

STEP2が分からないです……🥲︎

[@マルチーズ先生のやさしい東大数]

これが最小解だ！と宣言するだけです。STEP3以降で、それよりも小さい解が存在することを示していきます。