数学オリンピック史上最高難度 Vieta Jumpingで解く
Вставка
- Опубліковано 25 січ 2024
- こんにちは！マルチーズ先生です。1988年の数学オリンピックで出題された問題です。当時は難問とされていたようですが、今はVieta Jumpingという手法が浸透したため、それほどでもなくなったようです。
【マルチーズ先生のやさしい東大数学】
高校レベルから大学レベルまでの、面白そうな数学の問題を、週3回、火曜・金曜・土曜の19時配信予定。
数学パズル講師 マルチーズ先生
地元の県立高校を卒業後、東京大学理科いぬ類に入学。犬として初めて、東京大学大学院工学系研究科を卒業。現在は、大学入試問題過去問、積分問題、図形問題その他について、高校レベルから大学レベルまで幅広く扱い、youtubeで動画配信中。趣味は散歩とフリスビードッグ。
もう凄すぎて感動しちゃいました。こんな綺麗な編集の動画ありがとうございます。
このようなコメントをもらえると感動します！
平方数よりも平方数じゃないことを表現する方が難しいのに、あえて「平方数じゃないと仮定して降下法」で証明するのが、トリッキーな気がする
確かにそうですね。
平方数じゃないことが効果的に効いてるはずなのに証明中目立たない感じにヌルッと出てくるからビビる
思い出深い問題です、高校時代友人に誕生日プレゼントとして出された問題がこれでした。整数問題は得意な方で数オリの本戦の問題でも解くことができるぐらいだったのですが、この問題に関しては一ヶ月かけても解くことができなかったのを覚えています。解説を見てvieta jumpingを初めて知り、自分の未熟さを思い知ったのと同時にすごく感動した思い出があります。
思い出話を有難うございます。感銘しました！
解法自体はとてもすっきりしているのがポイント高いですね
有難うございます！
解と係数の関係で矛盾が出せるかもと気が付けば解けるんでしょうね。
大学入試でも誘導付きなら普通に出そうな感じがしますね。
数学オリンピックの難問って、解と係数の関係をアクロバティックに使わせるの好きですよね。それだけ重要な性質ということなんでしょうけどね。
思いつくかがカギですね。
1つ1つやってることは整数問題と背理法なので中3か高1くらいの内容なんだけど、自力で解け言われたら無理やな．．．
面白い良い問題だわ
そうなんですよね。思いつくことが大変です。
なるほどな
これはスッキリ
有難うございます！
ぱっと見難問なのに、答え自体は中学生とかでも理解できるのすげー
そうですね！
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 を持つって事実を暗黙に使用してるよね。
平方数になることの証明っていう一見行けそうな感じだから平方数にならないと仮定するのはクソ難しいな
思いつくのが難しいですよね。。。
整数は自信あったから数時間頑張ったけど無理だった。この方法を知れて感動した。
有難うございます。お役に立てて良かったです！
高校時代に無限降下法を初めて見た時、なんだこの証明法は！？って衝撃を受けたけど、ビエータジャンピングはその比じゃないくらい衝撃
有難うございます！
自然数x,y,zを用いて(x^2＋y^2＋z^2)/xyzとかける自然数を求めよという問題で悩んでいたとき、ふとvieta jumping を用いたらうまくいくかなと閃いて無事解けたのを思い出した
2006年の東大入試と似てますね。
@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
@anasuit1111さん何度もすみません。
vieta jumpingについてz=1の時は簡単にこのテクニックがつかえて有名なのは知っているのですが、一般のzについてこれが言えるかはかなり厳しいのではないかと思います。
出典についても色々と調べましたがこれに該当するものは見つけられませんでした。
これを見ている方でこの問題の解法を知っている方はぜひ教えてください🙇♀
@@sterben253
昨日書いたはずだけど消えてるようだからまた載せますね
ヒントとしては
①1≦x≦y≦zとしたときx^2＋y^2≧z^_2であることをjumpingを用いて示す。
②①を使って、問題の式が取りうる値を絞る
③その値一つ一つを吟味する
って感じです
最初は a,b={1,1}の場合のみa²+b²がab+1の倍数になるのではと予想したけど、その予想は見事に外れた。
プログラムで検証しか結果、まずb=a³の場合、(a²+b²)/(ab+1)=a²が常に成立することが分かりました。
さらに{8,30}、{27,240}、{30,112}など、いくつかの他の解も見つけましたので完全にお手上げです。
b=a^3の時のみ成立すると思ってましたが、他に解があったのですね！有難うございます。
@@user-dm2by4yh7w
いや、有限個しか解が存在しないなら、
「有限個しか解が存在せず、その全てで題意を満たす」
ということを証明すれば良いし、また、解は無限個存在するけどそれに対応する(a,b)に法則性があるなら、
「(a,b)がこのような法則性を満たしている時のみ題意を満たし、またそれ以外では題意を満たさない」
ということを証明すれば良いので、一般に(a^2+b^2)/(ab+1)が整数になる場合について証明するより簡単な可能性がありますよね？
だけど解は無限個ある上に法則性もいまいちよく分からなかった、って事でしょ
この動画の証明を精査すればわかるんですが、平方数kを固定したとき、解の組を一つ見つければそれより大きい解の組を得られます
k=n^2(≧4)とし、(A,B)をA
@@jalmar40298 すばらしいコメント有難うございます。この問題をコンプリートできた気持ちになりました！
@@JunyaS.
解が無限個あるかどうかは言及してないけど、規則性がわからないからお手上げだと、コメント読んだら分かるよ、わざわざ言い直す必要ない
ab+1で割り切れるという条件が活用できているのか、他の条件ab+2などでもできてしまうのでは？という疑問を感じつつよくわからなかったのでまた明日見に来ます
最初にあの分数式を自然数kとおいている時点で、割り切れるという条件を使っています
@@user-du1te7ks2w コメント有難うございます。その通りです。
有限群論とかでも見たことある証明方法ですね。条件を満たす最小の位数の群があると仮定して、それより小さい群があることを示すという論法。誘導も何もなしで見つけるのはそら無理でしょうｗ
専門的なコメント有難うございます！
難しいですね。
とっかかりが分からず、手も足も出ませんでした。
初めに解法を確立した人が凄いですよね。
解説聞けば私でも理解できるような問題なのに、著名な数学者が何人も集まっても解くことができないのか。いやはや、数学は奥が深いねぇ。
シンプルで難しいものが、本当に難しい。含蓄があります。
なるほど、いくらでも小さな解を生成できちゃうのが矛盾点なのね
無限降下法ですかね。
解の組み合わせとして、[n, n^3], [n^3, n(n^4-1)] を見つけたけど、それ以外にあるでしょうか。
すばらしい！
[n(n^4 - 1), n^3(n^4 - 2)]
@@chamakebin1023 すごい。どんどん出てきますね！
背理法の究極版って感じですね。。。
「解と係数の関係」＋「無限降下法」という感じでしょうか。
説明聞けばそこまで難しいことはしてないけど、思いつくの無理すぎる
何事も、最初に考えた人は偉いですね！
解説を聞いても解けるようになる気がしない
使うべき場面の見極めが難しそうですね。
無限降下法みたいな感じか
はい。「解と係数の関係」＋「無限降下法」ですね。
京大数学にも似たような過去問があったような気がするw
流石にここまで難しくはなかったけど
そうなんですね。
これみるたび思うけど、主張すごいよな.成り立ちそうにも一見見えないしvieta知らないとまず無理そうだし...
問題を考えた人、凄いですね！
はえー無限降下法って有能なんやな
そうですね。ちょっと不思議な感じがしますが、証明問題に有能ですね！
kが平方数ならx>=0、平方数でないならx>0。この差だけから「x>0での最小仮定に反する」って言うの、いくら何でも的が小さすぎる。数オリだとそのレベルなのかな？
これは流石に一度答えを見ないと一生辿り着ける気がしない…
そうですね。。。
やばすぎる これやばい やば
やばいです！
題意は(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が共に偶数と言えるのは何故ですか？
bc-Nが偶数であるということは
bcとNの偶奇が一致するということで、bc+Nも偶数であると考えられると思います
b±√cって必ずしも整数とは限らないんじゃ？
@@anasuit1111確かにそうですね、その場合は一意性が無いので積の形で進めていけませんか？難しいですね
最後の部分は
b^2-cとなり任意の整数cで整数となることは分かっており、整数は素因数分解できるので、cが必ずしも平方数とはいえませんね。
はぁ…
追いつけないねぇ
おもろい
シンプルで面白いですよね。
最小解とは何の数値に注目して最小と言ってるのかわかりません。
a + b ?
はい、通常は、a+bが最小になる場合です。例外があるかは、私も研究不足ではっきりとしたことは言えません。。。
仮定して矛盾点を出すの, 背理法みたい
その通りです。
あのTerence Taoが解けなかったと言う問題
私も結構考えたが解けませんでした笑
Terence Taoが解けなかったのですね。びっくり！
／(^o^)＼ﾜｶﾗﾝ
説明が拙く、スミマセン。。。
こんな難しい問題、どうやって作問しているんた…？
聞いてみたいですね。。。
よく分からんが凄い
有難うございます！
そんなのってありかよ...
vieta jump って何がジャンプなの？
vietaは、解と係数の関係を表します。最小解を設定したあと、vietaによって、さらに小さい解が得られるところを、jumpingと言っているのだと思います。
@@user-we9lp7lh4t なるほどね
言いたいことはわかるけど
高校生にこれ、、？
確かに難しすぎますよね。。。
無限降下法的な？
はい、「無限降下法」と「解と係数の関係」のハイブリッドですね。
解けないなら出すなよ...
優秀な受験生に解かせようとしたんですかね。。。
問題作成委員会の人が解けないのになんで答えあるんだ？全員解けないわけではないのか
スミマセン、説明を省いたのですが、数学オリンピックで解けた人が11名いたようです。おそらく、その方々の解法を整理して1つのテクニックにしたのだと想像します。
@@user-we9lp7lh4t 横からすみません。問題作成委員会の人が証明できてないなら、この主張が正しいかどうか分からず、問題として出せないはずじゃないかな？と思いました。正しいなら証明、正しくないなら反例を示せ、という問題形式なら成り立ちますが・・・・。
@@user-ic4tv1tc2d 私も不思議に思いました。だから最後の問題として出したのですかね。。。
作った人は作為があるので解がわかっているということかな
作者以外の委員会メンバーが解けなかったのではないか
@@p0utan はい、私のそのように想像してます。
オーストラリア問題作成委員会ちょっとこい
STEP2が分からないです……🥲︎
これが最小解だ！と宣言するだけです。STEP3以降で、それよりも小さい解が存在することを示していきます。
「AならばBである」この命題の待遇は「BでないのならばAではない」・・・提示された命題を証明したければ、その命題の待遇を証明する。数学論理の基本なのですが、これは「大学入試数学難問あるある」の「にっちもさっちも行かなくなったら、背理法を使え」というヤツです。「因数と式」の問題のように見えて、本質的には「命題と集合・論理」を理解しているかが重要。ところで、論破で有名なひろゆきにセンター数学過去問「命題と集合・論理」の設問を１０年分ぐらいやらせてみたら、果たして彼は満点が取れるのでしょうか。
面白いコメント有難うございます！