カーティスの定理

お願いです。カーティスの定理がどうしても証明できません。おそらく数学的帰納法で証明するのでしょうが、見通しがつきません。n=kの時成立すると仮定した時、n=k+1をどのように示せばよいかを教えてください。（できれば高校数学の範囲で）

ここでいうカーティスの定理とは、
「1/x1 + 1/x2 + 1/x3 + … + 1/xn ＜1
(但し、x1,x2,x3,…,xn(nは正の整数)は正の整数)
を満たす左辺の最大値を与えるx1～xnは、
x1=2 ,x(n+1)=Π(k=1～n)xk +1」
というやつです。

No.6 ベストアンサー 回答者： noname#101087 回答日時： 2009/03/08 20:59

>ある大学入試問題で、(自分が使っている表記を用いて)

>1/x1 + 1/x2 + … + 1/x(n-1) + 1/(xn -1) =1
>を示せ、というのがありました。

これは的に命中しそうです。 greedy algorithm (強欲算法？)の一種。

　1/2 + 1/2 = 1　　…(A1)
だから、
　1/2 + 1/3 < 1　　…(B1)
が「左辺の最大値を与える」分母セット。
この第一段階で、
>(1/a) = {1/(a+1)} + 1/{a*(a+1)}
すなわち、
　　(1/a) - {1/(a+1)} = 1/{a*(a+1)}
だから、(A1), (B1) のギャップは、
　　1/2 - 1/3 = 1/6

(あとは、同様の繰り返し)

　1/2 + 1/3 + 1/6 = 1　　…(A2)
だから、
　1/2 + 1/3 + 1/7 < 1　　…(B2)
が「左辺の最大値を与える」分母セット。
(A2), (B2) のギャップは、
　　1/6 - 1/7 = 1/42

　1/2 + 1/3 + 1/7 + 1/42 = 1　　…(A3)
だから、
　1/2 + 1/3 + 1/7 + 1/43 < 1　　…(B3)
が「左辺の最大値を与える」分母セット。………

>証明の焦点だけでも ..... 。
>n = k のとき、1 - Sk = 1/{x_(k-1)*x_k} になる。
>したがって、x_(k+1) = x_(k-1)*x_k + 1 が題意を満たす。

以上の口説き方は、かなりくどい感じがします。
きれいに整理してください。
　

No.10 回答者： stomachman 回答日時： 2009/03/11 04:28

面白い定理ですねえ。

結果はとても綺麗で分かりやすいし、一見自明にすら思えるのに、やってみるとすごく手強い。しばらく考えてみたんですが、まだまだ出来そうにありません。

　でも、「証明のreferenceが出てるようだけど、見ちゃったら詰まらんしな」という意見に賛成の方のご参考になるかも知れないと思い、これまで考えたことを書いておきます。

　ご質問の定理は「(回答No.6に出てくる言葉を使うと）強欲算法」が旨く行くことを主張しています。この定理が正しいとすると、逆数の合計を１に近づける代わりに、1/c (cは正の整数）に近づけるという問題を考えると、その場合にも「強欲算法」が旨く行くことは自明です。
　そこでさらに一般化して、逆数の合計を任意の有理数q(0 ＜q＜1)に近づける、という問題においても「強欲算法」が旨く行くのではないかと予想したんですが、これはもうn=2で反例が見つかりました。
　ってことは、この定理は有理数全体を考えてちゃ駄目で、もっと限定された集合の話に違いありません。

　正の整数の集合をNと書くことにします。
　n個の、1より大きい整数から成る列y = < y[1], y[2], ..., y[n]>の集合をY(n)とします。
∃y( y∈Y(n) ∧ r = Σ(1/y[j])) （"∧" は "and"の意味です。Σは　j=1～n）
という形に書ける有理数rは、もちろん
∃s∃ｔ(r = s/t ∧ t = Πy[j] ∧ s∈N) （Πは j=1～n)
を満たします（s/tは必ずしも既約分数ではない）。ただし、sはどんな数でも良いという訳ではありません。
　なので、分母がtのときに作れる分子sの集合をS(t,n)としましょう。ただし話をちょっと緩めて、tはΠy[j] の倍数であれば良いことにします。つまり、
S(t,n) = {s | ∃c∃y(y∈Y(n) ∧ c∈N ∧ t = cΠy[j] ∧ s = t Σ(1/y[j]) )}　　（ΠとΣは j=1～n)
です。これでも
r = Σ(1/y[j]) = s/t
であることには変わりありませんから。

　するとご質問の定理は、（有理数全体を考えてるのではなくて）専ら集合
{S(t,n)/t | t∈N}
の性質について語っているんだ、と見ることができます。

　さて、t(∈N)を割り切る正の整数（ただし、t自身は除く）の集合をF(t)とします。例えば、
F(45) = {15, 9, 5, 3, 1}
です。すると、
S(t, n) = {F(t)からn個の要素を重複を許して取り出したものの和}
となります。例えば、
S(45, 1) = F(45)
S(45, 2) = {30, 24, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2}
S(45, 3) = {45, 39, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3}
　これらのうちで、「s/t < 1であって、s/tが最大になるもの」をg(t,n)と書くことにすると、すなわち
g(t,n) = max{ s | s∈S(t,n) ∧ s< t}
であり、例えば
g(45,1) = 15
g(45,2) = 30
g(45,3) = 39
です。

　さらに
f(n) = max{g(t,n)/t | t∈N}
と書くことにすれば、ご質問の問題は要するに「f(n)は幾らか？」ということになります。（f(n)さえ分かれば、それに対応するyを構成するのは容易だからです。）
　で、それから先はまだ考えてないんです(笑)けど、この筋は定理の数列x[j]が互いに素になってることとナントナク絡んできそうな予感がしません？ね？

この回答へのお礼

すみません。いろいろあって皆さんの回答を見るのが遅れました。自分は、この定理自体は容易に理解できるからなんとかなるかなって思ってましたけど…(フェルマーの最終定理みたいなものですね)　どうやらとんでもないパンドラの箱を開けてしまったようです。すでに皆さんの回答の内容は自分の理解の範疇を超えていますが、なんとか調べながらもついていきたいと思います。

お礼日時：2009/03/11 22:45

No.9 回答者： noname#101087 回答日時： 2009/03/10 22:45

訂正！

1 を単位分数に展開する greedy algorithm では局所的極値を追うだけで、大局的極値とは限りませんので。

No.8 回答者： noname#101087 回答日時： 2009/03/10 22:41

#6 ですが、これは超難問らしいです。

1 を単位行列に展開する greedy algorithm では局所的極値を追うだけで、大局的極値とは限りませんので。

・カーチス論文は、木戸銭を払えば見れるようですね。
　　↓
　http://www.jstor.org/pss/2299023
/D. R. Curtiss, "On Kellogg's Diophantine problem" Amer Math. Monthly, 29, (1922), 380-387.

・余りの難解さに閉口したのか、別証明も見られます。
　　↓
　http://arxiv.org/pdf/math/0412480
/ p.12 Lemma 5.3

・ところで、分母の系列はシルベスター (Sylvester) 数列と言うみたいです。
　　↓
　　　　　 k<0～(n-1)>
　Sn = 1 + ΠSk
　　↓
　http://www.research.att.com/~njas/sequences/A000 …
>Sylvester's sequence: a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2

…というわけで、 greedy algorithm はチョン。

No.7 回答者： R_Earl 回答日時： 2009/03/10 17:10

ANo.1, ANo.4です。

> 1/x1 + 1/x2 + 1/x3 + … + 1/xn =1(xi≦x(i+1)(i=1,2,…,(n-1)))を満たす正の整数解のうち
> xnが最大のものの解が求められればそれに１を足せばいいというのを帰納法で…

> 1/a1 + 1/a2 + … + 1/an =1 (ai≦a(i+1))を満たす正の整数解のうちanが最大となる解が
> (a1,a2,…,an)=(x1,x2,…,(xn -1))
> だと証明できればいいのかなと思いました。

1/a1 + 1/a2 + … + 1/{ a(n-1) } + 1/an = 1 ( ai ≦ a(i+1) (i = 1, 2, …, n-1) )が成り立てば、
1/a1 + 1/a2 + … + 1/{ a(n-1) } + 1/{ (an) + 1 } < 1となるのは分かります。
しかしそれが『最大値である』かどうかは分かりません(anが最大値を取るとしてもです)。

例えば、次の2つの条件を満たす数列bn（値は自然数）が存在すると仮定します。

1/b1 + 1/b2 + … + 1/{ b(n-1) } + 1/bn > 1
1/b1 + 1/b2 + … + 1/{ b(n-1) } + 1/{(bn) + 1} < 1

この数列は

1/a1 + 1/a2 + … + 1/{ a(n-1) } + 1/{ (an) + 1 } < 1/b1 + 1/b2 + … + 1/{ b(n-1) } + 1/{(bn) + 1}

を満たす可能性があります
（特に二つの数列の末項を比較した時、an ≦ bnが成り立つなら必ず成り立ちます）。

そのような数列bnが存在しないと証明できれば良いのですが、
現時点では良い方法が思いつきません。

単位分数分解の問題なので、その方面で色々調べてみようかと思います。

No.5 回答者： noname#101087 回答日時： 2009/03/06 08:38

(1/a) = {1/(a+1)} + 1/{a*(a+1)}

No.4 回答者： R_Earl 回答日時： 2009/03/06 00:57

ANo.1です。

ANo.3さんの回答に少し気になる点があります。

> ｎ＝ｊのとき成立すると仮定すると、
> ｎ＝ｊ＋１のとき、
> 　　S(j+1)＝S(j)+1/x(j+1)

『S(j) = 1 - 1/y(j)』が真だとしても、
『S(j + 1) = S(j) + 1/x(j+1)』が真であるとは言い切れないと思います。

仮にS(3) = 1/2 + 1/3 + 1/7が真であると仮定します。
この時、S(4)の最初の3つの項が1/2と1/3と1/7であると言い切ってよいのでしょうか？
例えばS(3) = 1/2 + 1/3 + 1/7の時、
S(4) = 1/2 + 1/3 + 1/8 + 1/40となるかもしれません
（例えばの話です。「S(4) = 1/2 + 1/3 + 1/8 + 1/40」が偽であることはすぐに確認できます）。

S(n) = 1/a(1) + 1/a(2) + …… + 1/a(n)の時、
S(n+1) = 1/b(1) + 1/b(2) + …… + 1/b(n+1)という可能性も（現時点では）あります
（a(1), a(2), …, a(n)とb(1), b(2), …,　b(n+1)は正の整数）。

最終的にx(1) = 2, x(n+1) = Π(k=1～n)x(k) + 1となるようなので
数列a(n)とb(n)は全く同じ数列になるはずです。
しかし現段階ではa(n)とb(n)が同じであると証明されていません。

とりあえず、x(n+1) = { Π(k=1～n)(xk) } + 1だと仮定して少し考えてみましたが
（本当にこの解釈でよいのでしょうか？）、
ここに書いたようにa(n)とb(n)が同一だと(現時点では)いえないので、
数学的帰納法がうまく適用できていません。
ちょっと工夫すれば帰納法が適用できるのかもしれませんし、
実は帰納法で解くのは難しいのかもしれません。

a(n)とb(n)が同一であると証明できれば、
証明はほとんど終わったようなものなのですが…。

この回答への補足

ある大学入試問題で、(自分が使っている表記を用いて)
1/x1 + 1/x2 + … + 1/x(n-1) + 1/(xn -1) =1
を示せ、というのがありました。
これを用いれば、
1/a1 + 1/a2 + … + 1/an =1 (ai≦a(i+1))を満たす正の整数解のうちanが最大となる解が
(a1,a2,…,an)=(x1,x2,…,(xn -1))
だと証明できればいいのかなと思いました。
こんなことは証明可能でしょうか？

補足日時：2009/03/06 16:18

No.3 回答者： Mr_Holland 回答日時： 2009/03/05 23:09

　1/x(1) + 1/x(2) + 1/x(3) + … + 1/x(n) ＜1

(但し、x(1),x(2),x(3),…,x(n)(nは正の整数)は正の整数)
を満たす左辺の最大値を　S(n)　と置きます。

　x(1)=2, 　x(2)=3, 　x(3)=7, 　　x(4)=43,…
　S(1)=1/2, S(2)=5/6, S(3)=41/42, S(4)=1805/1806, …
となることから、S(n)　が

　　S(n)＝1-1/y(n)　　ただし、y(n)＝Π(k=1～n)x(k)

と書けるのではないかと当たりをつけ、これを数学的帰納法により証明します。

ｎ＝１のとき：
　　S(1)＝1-1/y(1) ＝1-1/x(1)　＝1/2　　で成立。

ｎ＝ｊのとき成立すると仮定すると、
ｎ＝ｊ＋１のとき、
　　S(j+1)＝S(j)+1/x(j+1)
　　　　　＝1-1/y(j)+1/x(j+1)　＜１
　∴x(j+1)＞y(j)　・・・・・・・・・・・（１）

　ところで、S(j+1)は、１未満の最大の数なので、1/x(j+1)は条件（１）を満たす中で最大でなければなりません。
　つまり、x(j+1)は条件（１）を満たす最小の正整数となりますので、
　　x(j+1)＝y(j)＋１　＝Π(k=1～j)x(k)＋１　　・・・・（☆）
でなければなりません。

　ここで、S(j+1)　の式に戻って、（☆）を利用して式変形を続けますと、
　　S(j+1)＝1-1/y(j)+1/x(j+1)
　　　　　＝1-{x(j+1)-y(j)}/{x(j+1)y(j)}
　　　　　＝1-1/y(j+1)
となり、ｎ＝ｊ＋１　のときも成立します。

　以上のことから、数学的帰納法により、S(n)は
　　S(n)＝1-1/y(n)　　ただし、y(n)＝Π(k=1～n)x(k)
と書けることが示されました。

　これにより、先ほどの証明の中で、ｎ＝ｊのときに成立すると仮定したときに得られた結論（☆）は、任意の正整数ｊ（つまり、ｎ）で成立することが言えます。

　従って、題意を満たす　x(n)　は次のように書けると言えます。

　　x(n+1)＝Π(k=1～n)x(k)＋１、　ただし、x(1)＝２



＃
＞n = k のとき、1 - Sk = 1/{x_(k-1)*x_k} になる。

　ｋ＝３のとき　1-41/42　≒　1/(3*7)　で成立しないと思うのですが。

No.2 回答者： noname#101087 回答日時： 2009/03/05 19:23

>おそらく数学的帰納法で証明するのでしょうが、見通しがつきません。

n=kの時成立すると仮定した時、.....

1/x1 + 1/x2 + 1/x3 + … + 1/xn = Sn としましょう。

証明の焦点だけでも ..... 。

n = k のとき、1 - Sk = 1/{x_(k-1)*x_k} になる。
　したがって、x_(k+1) = x_(k-1)*x_k + 1 が題意を満たす。
　

No.1 回答者： R_Earl 回答日時： 2009/03/05 15:00

> おそらく数学的帰納法で証明するのでしょうが、見通しがつきません。

> n=kの時成立すると仮定した時、n=k+1をどのように示せばよいかを教えてください。（できれば高校数学の範囲で）

自力でどこまで解いたのかを書かないと、
質問自体が削除されます。

質問者さんはどのようにして、
「n = k + 1の時に成り立つ」ことを
証明しようとしたのでしょうか？
失敗例で良いので、それを書いて下さい。
どこでどう行き詰ったのかを書いて下さると、
アドバイスしやすくなるかもしれません。

それから、もう1点。

> x(n+1)=Π(k=1～n)xk +1

Πは積の記号ですよね。
このΠはどこまでかかるのでしょうか？
{ Π(k=1～n)(xk) } + 1でしょうか？
Π(k=1～n){ (xk) + 1 }でしょうか？

この回答への補足

{ Π(k=1～n)(xk) } + 1 です。

数学的帰納法でどうしようと思っていたかというと、
そもそもこの定理をとある本で見た時に、「たとえばn=3で考えた時
1/x1 + 1/x2 + 1/x3 =1 (x1≦x2≦x3)の正の整数解(x1,x2,x3)のうち
x3が最大となる解は(2,3,6)で、カーティスの定理を考えた時に
x3=6+1　の形になっている」のようなことを書いていたので、どうやら
1/x1 + 1/x2 + 1/x3 + … + 1/xn =1(xi≦x(i+1)(i=1,2,…,(n-1)))を満たす正の整数解のうちxnが最大のものの解が求められればそれに１を足せばいいというのを帰納法で…　と考えているうちに分からなくなりました。

補足日時：2009/03/06 08:29