ふと、数学オリンピックのHPを見てみると、数学オリンピック本選問題が掲載されてるのね。
予選の時は、結構、すぐに掲載されてたけど、本選は掲載まで時間がかかるのどうしてだろう？？
ちなみ、問題はこちら
2008年日本数学オリンピック本選なんか、これを見つけてしまっては、解かざるをえないのだろうか。
何しろ、予選を解答してしまったので、本選もやらなければ何か気持ち悪いし、だからと言って、難問とは言えども解こうとしてわかりませんでしたじゃ、格好悪すぎる・・・
しかし、理学部数学科出身としてのプライドにかけて、解いてみることにします・・・
まぁ、やはり予想通り難問の連続ですね。
本選の問題は計5問を4時間で解く。
1問当たり、48分。
予選を突破した100人前後の数学猛者が試験に挑戦して、5問中2問完答すればほぼ本選通過20名になるというのだから、それだけ難問が揃っていると理解して間違いない。・・・と言い訳してみました。
1問当たり、48分とは言いましたが、実際には1時間はかかると思って間違いはないでしょうね
この問題は比較的ラッキー問題かもしれませんね。
まず、P(x)に（ｎの2乗）を代入すると、0になるのだから
は容易に理解できると思います。
もちろん、P(x)は整数係数多項式なので、
Q(x)も当然、整数係数多項式です。
ここからは、背理法で示します。
ある有理数ａの時に、P(aの２乗)＝１であったと仮定する。
ａは有理数なので
とおける。p,qは互いに素な0でない整数。
これを代入すると
ここまでは、すんなり行けた人も多いと思います。
ここで、どんな矛盾を示してやればいいかという事ですね？
これを、
無限降下法を使って示します。
（無限降下法は
こちら）
これを、両辺を（ｐの２乗）で割ると
ｐは整数なので、これらの両辺は整数でなければならない。
従って、
ｔは（ｐの２乗）で割り切れる数である。
従って
よって
は成立せず、よって題意が満たされたことになる。
この問題はラッキーと言ったが、あくまで数学オリンピック本選においての話。
背理法を二重に使うとやはり混乱もしかねないが、整理整頓すれば、特に引っかかる点はないだろうと思います。
ま、私の答えが合ってたらの話ですけど・・・
よろしければ、クリックお願いします⇒
「数学ブログ」
ついでに、こちらも参加しております⇒
「人気ブログランキング」
« 2008年日本数学オリンピック本選 第二問 l ホーム l 素数は無限の彼方に・・・ »
別な証明方法を見つけました。
背理法を使って、(a^2 - n^2) Q(a^2) = 1 とする所までは同じです。
証明
a = c/b (b,cは互いに素)とおく。
上の式にこれを代入し、両辺に b^2 を掛けて、
(c^2 - b^2 n^2) Q(c^2 / b^2) = b^2 ---(A)
とする。
ここで c^2 - b^2 n^2 , b^2 は整数なので、
Q(c^2 / b^2)も整数でなければならない。
また、b^2 は c^2 - b^2 n^2 を割らないので、
(A)より b^2 は Q(c^2 / b^2) を割らなければならない
(もし割らないならば、ある整数 w によって c^2 - b^2 n^2 = w b^2 となる。
このとき c^2 = b^2 (n^2 + w) となるが、これは「b,cは互いに素」に反する。
仮定から、b^2 , c^2 も互いに素だからだ)。
多項式Qの第i項目の係数をq_i (iは 0 <= i <= m を満たす添字)とおくと
q_i は b^(2i+2) で割り切れる
(2i は代入による c^2 / b^2 の分母の b^(2i) を約すため。
+2 はQ(c^2 / b^2) がさらに b^2 で割れなければならないため)。
よって、 q_i = r_i * b^(2i+2) なる整数たち r_i が存在する。すると(A)は
(c^2 - b^2 n^2) R(c^2) = 1
( R(c^2) は項 r_i c^(2i) を i=0 から i=m まで足し上げたもの )
となる。
ここでようやく平方数の出番が来る。上の式を
(c + b*n) (c - b*n) R(c^2) = 1
と変形する。右辺が 1 なので、
|c + b*n| , |c - b*n| , |R(c^2)| (どれも整数の絶対値) は全て 1 でなければならない。
さて、 c = 0 , b = 1 でない限り |c + b*n| , |c - b*n| のどちらかが 1 でなくなるが、
c = 0 は仮定に反するので、
どうしても |c + b*n| , |c - b*n| のどちらかが 1 でなくなる。矛盾が起こった。
証明終わり。
はじめまして、コメントありがとうございます。
証明法に関して、大筋正解と言っていいと思います。
ただ、
「多項式Qの第i項目の係数をq_i (iは 0 <= i <= m を満たす添字)とおくと
q_i は b^(2i+2) で割り切れる 」
という部分に関して、少しだけ、しこりが残りました。
例えば、＝１の時、要するに整数係数多項式Ｑ（ｘ）のｘの係数が、（ｂの３乗）で
割れてしまうのは何故なのでしょうか？
数式をテキストで書いてくださった為、私自身が理解できていないのかも
しれません・・・そのときは、すいません・・・
整数係数多項式Ｑ（ｘ）にｘ＝c^2 / b^2 を代入する時、結果としてＱ（ｘ）が
整数になる必要はありますが、各項が整数になっている必要はありませんよね？
教えていただければ幸いです。
こういった問題は、ｂやｃのように数を文字で置き換える場合、
置き換える文字の条件を正確に書かなければ、しこりが残ってしまいますね。
私は、難問が難問たる所以と思うのはこういう部分にあります。
> 割れてしまうのは何故なのでしょうか？
すみません、ここの文意がつかめませんでした。
> 整数係数多項式Ｑ（ｘ）にｘ＝c^2 / b^2 を代入する時、結果としてＱ（ｘ）が
> 整数になる必要はありますが、各項が整数になっている必要はありませんよね？
確かに……そうですね……。
この事(各項が整数)に対して、反例が見つけられそうです。
しかし、この事が偽であっても、証明はうまく行くようです：
(A)を再掲： (c^2 - b^2 n^2) Q(c^2 / b^2) = b^2 .
ここで b^2 は(最初のコメントで述べたように) Q(c^2 / b^2) を割る。
よって Q(c^2 / b^2) / b^2 は整数なので
(c^2 - b^2 n^2) { Q(c^2 / b^2) / b^2 } = 1 .
ここからは「ここでようやく平方数の出番が来る。」以下と同じ議論を行う事ができる。
証明終わり。
今度こそ、示せたはずです。
証明の穴をご指摘いただき、ありがとうございます。
再度、コメントありがとうございます。
昨日は、実は、あまりじっくりコメントを読めてなかったのですが、今日、
改めて、読ませていただきました。
証明の流れそのものは、コンパクトなのですが、少し問題を発見いたしました。
まず、はじめに
「a = c/b (b,cは互いに素)とおく。
上の式にこれを代入し、両辺に b^2 を掛けて、
(c^2 - b^2 n^2) Q(c^2 / b^2) = b^2 ---(A)
とする。」
ここまでは、全く問題なしです。
この次の文章。
「ここで c^2 - b^2 n^2 , b^2 は整数なので、
Q(c^2 / b^2)も整数でなければならない。」
確かに、c^2 - b^2 n^2 は整数です。
そして、b^2 も整数です。
しかし、だからといって、 Q(c^2 / b^2) は常に整数であるとは限りません。
例えば、もしも
c^2 - b^2 n^2 = 16
b^2 = 4
ならば
Q(c^2 / b^2) = 1/4
になると思われます。
この時点では、Q(c^2 / b^2) は整数になるかどうかは確定していないので
、整数になるのであれば、その証明が必要になります。
それにしても、こういうコメントはすごいうれしいですね。
こういう議論ができると、自分の解答を見直すきっかけになりました。
ありがとうございます。
ああ凡ミス……。うーん、この方法で示すための策が尽きました。
証明の流れが
「D:一意分解整域, F:Dの商体, 任意の f in D[X] (f は D の元を係数とする多項式環に属する),
任意の g,h in F[X] (g,h は F の元を係数とする多項式環に属する);
f = gh ==> ある l in F が存在して
f = (l*g)(l^(-1) *h) (l*g , l^(-1) *h は D[X] に属する) となる。
つまり、F[X]で可約 ==> D[X]で可約」
に似ているな(両辺を整数の式へと式変形した後、整除で式を整える所が)と思い、
まあこの流れなら上手く行くだろうと判断して失敗しました。
記事の証明を読ませていただきました。
すみません、実は、記事を途中までしか読んでいませんでした。
途中まで呼んで自分の証明に没頭して、結局誤った証明を書いてしまいました。
以下2つの事を書きます：
(i) 記事の証明に怪しい点がある事
(ii) (自分でもしつっこいと思いますが)別の証明を考えた事
(i)
「 q^2 - p^2 n^2 が p^(2m) の約数と仮定すると
p^(2m) = t (q^2 - p^2 n^2) と書ける。
t は自然数で、もちろん p の約数です。」
t は p^(2m) の約数ですが、
t が p の約数であるとは限らないのではないのでしょうか。
完全な反例は作れていませんが、
m >= 1 , p = 6 , t = 4 の場合、
t は p^(2m) の約数ですが、 p の約数ではありません。
なので、この部分の主張の証明が欲しいのです。
(ii)
「 q^2 - p^2 n^2 が p^(2m) の約数と仮定すると
p^(2m) = t (q^2 - p^2 n^2) と書ける。」
の所までは同じです。
証明
p^(2m) , t , q^2 - p^2 n^2 はどれも整数である事に注意する。
ここで p^(2m) は q^2 - p^2 n^2 を割らない
(もし割るならば、ある整数 s が存在して s p^(2m) = q^2 - p^2 n^2 となる。
このとき (s p^(2m-2) + n^2) p^2 = q^2 となるが、これは「 p,q は互いに素」に反する)
ので、 p^(2m) は t を割る。
両辺を p^(2m) で割ると
1 = (t / p^(2m)) (q^2 - p^2 n^2) (t / p^(2m) は整数) ---(B)
となる。ここからは
(最初のコメントでの)「ここでようやく平方数の出番が来る。」以下と同じ議論を行う事ができる。
(文字のおき方、式の形が変わっているので、この議論をもう一度行う。
(B)を 1 = (t / p^(2m)) (q+p*n)(q-p*n) と式変形する。
左辺が 1 なので、
|t / p^(2m)| , |q+p*n| , |q-p*n| (どれも整数の絶対値)は全て 1 でなければならない。
さて、 q = 0 , p = 1 でない限り |q + p*n| , |q - p*n| のどちらかが 1 でなくなるが、
q = 0 は仮定に反するので、
どうしても |q + p*n| , |q - p*n| のどちらかが 1 でなくなる。矛盾が起こった)
証明終わり
実は、仮定から出る「p^(2m) = t (q^2 - p^2 n^2)」と
上で得られた「t / p^(2m) は整数」を用いて
Q(q^2 / p^2) = p^2 / (q^2 - n^2 p^2) = (p^2)*( t / p^(2m) )
が整数である事が分かります。
つまり、私の2回目のコメントでの証明は正当化されます。
しかし、Q(q^2 / p^2) が整数である事の証明をするより、
今行った証明で終わらせる方が短く済みます。
そうですね、私の証明も誤りがありますね。
ｔは素数であれば成り立ちますが、ｔは素数かどうかはわかりませんね。
ですので、私も記事の内容を変更しましたので、また読んでいただけると
幸いです。
あと、通りすがりさんの証明ですが
「p^(2m) , t , q^2 - p^2 n^2 はどれも整数である事に注意する。
ここで p^(2m) は q^2 - p^2 n^2 を割らない
(もし割るならば、ある整数 s が存在して s p^(2m) = q^2 - p^2 n^2 となる。
このとき (s p^(2m-2) + n^2) p^2 = q^2 となるが、これは「 p,q は互いに素」に反する)
ので、 p^(2m) は t を割る。」
とありますが、
「p^(2m) は t を割る。」
のではなく、
「 t は p^(2m) を割る。」
ではないでしょうか？
ですので、またこの後の議論が変わってきます。
私の証明もあわせてご返事いただきたいです。
よろしくお願いします。
> のではなく、
> 「 t は p^(2m) を割る。」
> ではないでしょうか？
確かに、12 = 3*4 だからといって「12 は 4 を割らないので、 3 を割る」
と言うのはおかしいですね。
新たな証明を読ませていただきました。
無限降下法という論法は初めて見ました。
「上向きの」数学的帰納法は自然数の青天井性(n in 自然数 ==> n+1 in 自然数)
により矛盾なく(公理として)認められる一方、
「下向きの」無限降下法は自然数に底(1 or 0)がある事を利用して矛盾を導く、
という感じでしょうか。
非常に上手い論法です。
しかし、一方、ちょっと乱暴な所があるように見えます。
無限降下法自体にではなく、無限降下法を適用するために用意する命題の方に、です。
「これより、 p^(2m) = t (q^2 - p^2 n^2) を満たす
整数 m,t が存在する時、
m > m_1 , t > t_1 で
p^(2 m_1) = t_1 (q^2 - p^2 n^2) を満たす
整数 m_1, t_1 が存在する。」
とありますが、これは m=0 のときには「これより」の指す論法は使えません。
すなわち：[[ m=0 の時 p^(2m) = t (q^2 - p^2 n^2) は
1 = t (q^2 - p^2 n^2) となる。両辺を p^2 で割ると
p^(-2) = t (q^2 / p^2) - t n^2 となる。
p^(-2) は一般に整数ではないので、t (q^2 / p^2) も一般に整数ではない。
従って、一般に t は p^2 では割り切れない。
よって、一般に t = t_1 p^2 (t_1 は整数) とはおけない ]]
という風に。
m=0 は自然数の底である事に注目して下さい。
無限降下法を適用するために用意する命題の証明の中には、
まず間違いなくこいつが出てくるはずです。
そして、 m=0 の所まで「降りて来る」と、
無限降下法を適用するために用意する命題は成り立たなくなる……。
無限降下法自体には問題はないでしょう。
しかし、無限降下法を適用するために用意する命題の方は、証明できるのでしょうか？
(無限降下法を適用するために用意する命題が有限回で破綻するからこそ、
この論法は意味を持つわけですが、しかし……堂々巡り？)
ちょっと混乱しています。
どのように定式化すれば、無限降下法は正当化できるのでしょうか
(正直、これは重箱の隅をつつくような指摘ですね。無限降下法はは正しい「べき」です。
認めてしまえば、証明をとても鮮やかに結ぶ事ができますし)？
安全な範囲内で証明を書く事は可能です：
証明
m > 0 ならば、
「整数 m,t が存在する時、
m > m_1 , t > t_1 で
p^(2 m_1) = t_1 (q^2 - p^2 n^2) を満たす
整数 m_1, t_1 が存在する。」
では、新たな記事で使われていた論法で、実際に m=0 まで降りてみる。
この時 1 = t_m (q^2 - p^2 n^2) となる
(t_m の m は、新たな記事で使われていた論法を m 回適用した事を表す添字)。
ここからは
(最初のコメントでの)「ここでようやく平方数の出番が来る。」以下と同じ議論を行う事ができる。
すなわち：[[
上の式を 1 = t_m (q+p*n)(q-p*n) と変形する。
左辺が 1 なので、
|t_m| , |q+p*n| , |q-p*n| (どれも整数の絶対値)は全て 1 でなければならない。
さて、 q = 0 , p = 1 でない限り |q + p*n| , |q - p*n| のどちらかが 1 でなくなるが、
q = 0 は仮定に反するので、
どうしても |q + p*n| , |q - p*n| のどちらかが 1 でなくなる。矛盾が起こった ]]
証明終わり
確かに、無限降下法の定式化・正当化と言われると、少し難しい点があります。
まず、無限降下法の本質は、「無限に減少する数列がとれる」事、「自然数は
有界である」事、この二つの事実に矛盾が生じる事です。
それと、前回の通りすがりさんのコメントを引用させていただきます。
「とありますが、これは m=0 のときには「これより」の指す論法は使えません。
すなわち：[[ m=0 の時 p^(2m) = t (q^2 - p^2 n^2) は
1 = t (q^2 - p^2 n^2) となる。両辺を p^2 で割ると
p^(-2) = t (q^2 / p^2) - t n^2 となる。
p^(-2) は一般に整数ではないので、t (q^2 / p^2) も一般に整数ではない。
従って、一般に t は p^2 では割り切れない。
よって、一般に t = t_1 p^2 (t_1 は整数) とはおけない ]]
という風に。」
とありますが、まず、ｍは自然数なので最小の値は1ですね。
ですので p^(-2) という数字は考える必要がありませんよね。
また、無限降下法はあくまで、有限であるべき数の列が無限に存在してしまう
という矛盾性が本質なので、「 ｍ＝1 の時」のような具体的な数を当てはめて
検証する必要はないです。
ですので、
「実際に m=0 まで降りてみる。
この時 1 = t_m (q^2 - p^2 n^2) となる」
という検証は、無限降下法では必要ありませんね。
（ちなみに、0 は自然数でないので、またこの説明内容も変わってきます）
リンクの変更をお願いします。
P(x)は整数係数多項式なので、Q(x)も当然、整数係数多項式
はどうしてですか？
引越し、お疲れ様です。
リンク設定しときました。
高校生＞
コメントありがとうございます。
鋭いところに目をつけましたね。
高校生なのに感心だな～と思いつつ、冷静に考えれば、この問題を解くのは
皆、高校生なんだと考えると複雑な気持ちです。
「P(x)は整数係数多項式なので、Q(x)も整数係数多項式になる」
という部分
因数分解の練習している時に、この事実は経験として感じれるだろうと
思いますが、数学的には証明になってませんね。
実は、これをちゃんと書こうと思うテキストではうまく書けないので
簡単に書きます。
Ｐ(x) を n 次の多項式とします。
すると、必然的にＱ(x) は n-1 次の多項式になりますね
そして、Ｐ(x) において（ｘのｍ乗）の係数を a(m)とおきます。
もちろん a(m)は整数。
Ｑ(x)の（ｘのｍ乗）の係数を ｂ(m)とおきます。
この時点では、ｂ(m)が整数かどうかはわかりません。
しかし、(x-t)Ｑ(x)のカッコを外すと、Ｐ(x) になるわけです。
すると、a(m)とｂ(m)で連立漸化式がたてられます。
そして、これを数学的帰納法で証明することになります。
問題はｂ(m)が整数になるかどうかなので、漸化式を解く必要はありません。
紙に書くと、簡単に理解できると思います。
r＝n^2，P(x)＝Σ[i＝0～m]pix^iとするとき、P(r)＝0だから
P(x)＝P(x)－P(r)＝Σ[i＝0～m]pi(x^i－r^i)＝(x－r)Σ[i＝0～m]pi(x^i－r^i)/(x－r)
オイラーさんの解答についてですが、無限降下法を使ったこの解答は間違っています。オイラーさんの解答では、「P(n^2)＝0」であることが使われていません。条件を「P(n)＝0」に変えても同様に証明できてしまいます。ところが、この場合は反例が存在します(P(x)＝x－3,a＝2)。
なぜnではなく「n^2」なのか考えなければいけません。
通りすがりさんの解答が正しいです。n^2,a^2という数から｜q＋p*n｜，｜q－p*n｜という項が出てきて、これらが両方とも1でなければならないのに、それは矛盾を起こします。これが「n^2」の理由のはずです。
＞これより、p^{2m}＝t(q^2－p^2n^2)を満たす整数m、tが存在するとき
↑ここは「自然数m、整数t」としなければいけません。同様に
＞ m＞m1、t＞t1でp^{2m1}＝t1(q^2－p^2n^2)を満たす整数m1、t1が存在する。
↑ここも「自然数m1、整数t1」としなければいけません。つまり、
これより、p^{2m}＝t(q^2－p^2n^2)を満たす自然数m、整数tが存在するとき
m＞m1、t＞t1でp^{2m1}＝t1(q^2－p^2n^2)を満たす自然数m1、整数t1が存在する。…(*)
としなければいけません。もし(*)が証明できたなら、無限降下法が使えることになって証明が完成しますが、実際には、(*)は証明できません。なぜなら、m1が自然数であることが証明できないからです。m1＝m－1と置いた場合、m1はいつでも自然数になるわけではないでしょう。いつでも自然数になるなら(*)が証明されますが、m1はいつでも自然数になるわけではありません。
無限降下法を使った証明の有名なものとして、フェルマーの大定理のn＝4の場合がありますが、あの証明では、ちゃんと「いつでも自然数になる」ことが証明されます(だから無限降下法で矛盾する)。
というか、1つ上の米でも書きましたが、(*)が証明できるなら、条件を「P(n)＝0」と変えた場合でも同様に証明できてしまいます。しかし、P(n)＝0とした場合は反例があるのです。