「数論20050831022232」の編集履歴（バックアップ）一覧はこちら

「数論20050831022232」(2005/11/05 (土) 04:01:22) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

> 253 名前：１３２人目の素数さん[sage] 投稿日：2005/08/31(水) 02:22:32
> 数列{f(n)}はf(0)＝0，f(1)＝1，f(n＋1)＝f(n)＋f(n－1) (n＝1，2，3…)を満たす。
> A＝{f(i)｜i＝0，1，2，…}とおく。以下の問いに答えよ。
> (1)B＝{Σ[i＝1～∞]f(xi)｜自然数列{xn}は有限項を除いて0}＝Σ[i＝1～∞]Aとおく。B＝N∪{0}を示せ。
> (2)C＝{Σ[i＝1～∞]f(xi)｜自然数列{xn}は有限項を除いて0であり、xi＝xjならばxi＝xj＝0}
> ＝(Aの異なる元を有限個足した数全体の集合)⊂Bとおく。C＝N∪{0}を示せ。
> (3)自然数mに対して、Bm＝{Σ[i＝1～∞]f(xi)｜自然数列{xn}は、第m＋1項目から全て0}
> ＝Σ[i＝1～m]A ⊂B とおく。集合系{Bm}には極限集合が存在し、lim[m→∞]Bm＝B と
> なることを示せ。また、Bm＝N∪{0}を満たす自然数mは存在するか？

> 255 名前：253[sage] 投稿日：2005/08/31(水) 12:19:00
> ちょっと表現に不都合が…
> >>253に出てくる「自然数列{xn}」は、全て「非負整数列{xn}」に置き換えて下さい。

* 解答
> 256 名前：１３２人目の素数さん[] 投稿日：2005/09/01(木) 19:12:17
> >>253
> (1) 1をいっぱいつかっていいので簡単
> (2) 任意の自然数(正の整数とする)が異なるフィボナッチ数列内の数の和で表示できるという
> 意味と解してa≦xnなる自然数aは可能であることをnに関する帰納法でしめす。
> (I)n=0のときa≦x0=0なる自然数aは存在しないゆえ成立。
> (II)n=1のときa≦x1=1ならa=1ゆえ成立。
> (III)n≧2に対しn未満まで正しいとしてa≦xnをとる。a≦x(n-1)なら帰納法の
> 仮定からよい。x(n-1)＜a≦xnのときは0＜a-x(n-1)≦xn-x(n-1)=x(n-2)ゆえ
> a-x(n-1)=∑y(i)、y(i)は相異なるフィボナッチ数列内の数がとれる。a-x(n-1)≦x(n-2)
> ゆえy(i)の中にx(n-1)は入らない。よってaも相異なるフィボナッチ数列内の数の和で表示可能。
> (I)～(III)で示された。
> (3)F={x(i)|i≧1}とおく。n≧3にたいして単調増大有限列y1<y2<･･･<ykが
> ∑yi=-1+xn、yi∈Fをみたすときk≧[(n-1)/2]をみたすことを示す。
> (I)n=3,4なら[(n-1)/2]=1ゆえ明らか。(∵yiの項数は1以上。)
> (II)n≧5にたいしてn未満についての主張を仮定する。単調増大有限列y1<y2<･･･<ykが
> ∑yi=xn-1、yi∈Fをみたすと仮定する。yk<x(n-1)のとき∑[1≦i≦n-2]x(i)=-1+xnにより
> k=n-2、y(i)=x(i)でなければならない。このときk=n-2＞(n-1)/2≧[(n-1)/2]ゆえ成立。
> yk=x(n-1)のときは∑[i<k]y(i)=-1+xn-x(n-1)=-1+x(n-2)。よって帰納法の仮定よりk-1≧[(n-3)/2]。
> よってk≧[(n-1)/2]。
> (I),(II)で示された。

> 287 名前：名無しさん＠そうだ選挙に行こう[] 投稿日：2005/09/11(日) 16:02:00
> >>277
> >>253
> こんな解答ができた。
> (3)問題を次によみかえる。
> 　
> ＠＠＠＠　問題　＠＠＠＠
> x(i)をフィボナッチ数列、つまりx(1)=1,x(2)=1,x(n+2)=x(n+1)+x(n) (n≧0)とする。
> 有限個をのぞいて全部0である非負整数列の集合をCとする。J(c)を∑c(i)でさだめ
> n∈Nに対してE(n)をmin{J(c) | ∑c(i)x(i)=n}でさだめる。{E(n)}は有界でないことをしめせ。
> 　
> ＠＠＠＠　解答　＠＠＠＠
> c∈Cに対してJ’(c)をJ(c)-(1/2)#{i | c(i)=1}でさだめ、n∈Nに対しE’(n)を
> min{J’(c) | ∑c(i)x(i)=n}で定める。次は綺麗な証明が見つからないのでみとめる。
> 　
> 補題　任意のnとn=∑c(i)x(i)であるc∈Cにたいしてc’∈Cで
> n=∑c(i)x(i)、J’(c’)≦J’(c)、c’(i)≦1 (∀i)なるc’がとれる。
> 　
> これをみとめる。F(n)をmin{#I | ∑[i∈I]x(i)=n}でさだめる。すると
> (1/2)F(n)≦E’(n)≦E(n)が成立する。実際補題よりE’(n)=J’(c)、c(i)≦1である
> c(i)がみつかる。このとき∑c(i)x(i)=∑[c(i)=1]x(i)より∑c(i)≧F(n)。さらにJ’(c)の定義と
> c(i)≦1より∑c(i)=2J’(c)。∴(1/2)F(n)≦E’(n)。一方でJ’(c)≦J(c)からE’(n)≦E(n)は明らか。
> さて>>256によりF(x(n)-1)≧[(n-1)/2]である。（ちなみに“＝”になる。）
> よってE(x(n)-1)≧(1/2)[(n-1)/2]であるからE(n)は有界でない。
> 　
> 補題の証明なんだけど結構ながい。書く気にならん。どうしたもんだろ。

> 289 名前：253[] 投稿日：2005/09/11(日) 23:04:43
> >>256
> (1)，(2)大正解です。
> >>287
> うおお…合ってそうだが俺には判断できぬ。
> 
> 一応、考えていた(3)の解答を書いておきます(概要のみ)。
> m∈Nを、Bm＝N∪{0}が成り立つ自然数とする。このとき、V＝Σ[a∈Bm－{0}]1/aは発散する
> ことになる(Σ[a∈N]1/aは発散するので)。ところが、
> V≦Σ[ki＝0～∞ (i＝1，…，m)，(k1，k2，…，km)≠0]1/{f(k1)＋f(k2)＋…＋f(km)}
> 及びf(n)～α^n (α＝(1＋√5)/2)及び相加相乗平均の不等式などにより、Vは収束することが
> 分かり、矛盾。
> 
> 余談ですが、Vが収束することから、lim[n→∞]#(Bm∩[1，n])/n＝0となることも分かります。
> N全体に占めるBmの割合はゼロであって、実は かなりスカスカの集合になっている感じ。f(n)の
> オーダーが指数関数だから、高々m個足したところで、Nのほんの一部しか表せない、ということかな。

> 290 名前：名無しさん＠そうだ選挙に行こう[sage] 投稿日：2005/09/11(日) 23:18:23
> >>287
> 長い証明上等。読んでみたいから気合いいれて書いてちょ。

> 296 名前：287[sage] 投稿日：2005/09/12(月) 23:06:58
> 清書してみたらもっと綺麗な解答がみつかった。
> 再度用語の整理。x[i] (i≧1)はフィボナッチ数列。Cは有限個をのぞいて0の非負整数列の集合。
> このとき次が成立。
> 　
> 補題　c∈Cにたいしてc’∈Cを∑c[i]x[i]=∑c’[i]x[i]、∑c’[i]≦∑c[i]、c’[i]≦1を
> みたすものがとれる。
> 　
> 証明　Z×Zの元とみなしてここにに辞書式順序をいれる。
> (u,v)=(∑c[i]^2,min{i|c[i]≧2)をZ×Zの元とみなしてこの順序に関する帰納法。
> u=0ならあきらか。(u,v)<(U,V)まで成立するとして
> (u,v)=(U,V)と仮定する。∀i c[i]≦1ならc’=cとすればよい。∃i c[i]≧2と仮定する。
> CaseI)∃i c[i],c[i+1]>0のき。このときはiをc[i],c[i+1]>0、c[i+2]=0となるiがとれる。
> d∈Cをd[i]=c[i]-1、d[i+1]=c[i+1]-1、d[i+2]=c[i+2]+1、d[j]=c[j] (j≠i,i+1,i+2)
> で定める。このとき∑d[i]x[i]=∑c[i]x[i]、∑d[i]＜∑c[i]、∑d[i]^2＜∑c[i]^2
> であるから帰納法の仮定より題意をみたすc’が存在する。
> CaseII) CaseIでなくc[1]≧2 or c[2]≧2のとき。
> このときc[1]=0 or c[2]=0である。
> d∈Cをd[1]=c[1]+c[2]-1、c[1]=1、d[j]=c[j] (j≠1,2)
> で定める。このとき∑d[i]x[i]=∑c[i]x[i]、∑d[i]=∑c[i]、∑d[i]^2＜∑c[i]^2
> であるから帰納法の仮定より題意をみたすc’が存在する。
> CaseIII) CaseI,IIでないとき。
> i=min{i|c[i]≧2}とおく。このときi≧3でありc[i-1]=c[i+1]=0。
> d∈Cをd[i-2]=c[i-2]+1、d[i-1]=0、d[i]=c[i]-2、d[i+1]=1
> で定める。このとき∑d[i]x[i]=∑c[i]x[i]、∑d[i]=∑c[i]、∑d[i]^2≦∑c[i]^2
> であり、最後の不等号の等号成立は(c[i-2]、c[i-1]、c[i]、c[i+1])=(1,0,2,0)
> のときのみである。このときは(d[i-2]、d[i-1]、d[i]、d[i+1])=(2,0,0,1)。
> よっていづれにせよ(∑d[i]^2,min{i|d[i]≧2)＜(∑c[i]^2,min{i|c[i]≧2)であるから
> 帰納法の仮定より題意をみたすc’が存在する。□
> （続く）

> 297 名前：１３２人目の素数さん[] 投稿日：2005/09/12(月) 23:08:19
> （続き）
> 主張 E(n)=min{∑c[i]|∑c[i]x[i]=n}、F(n)=min{∑c[i]|∑c[i]x[i]=n、c[i]≦1}で
> さだめるときE(n)=F(n)。
> 　
> 証明 E(n)≦F(n)はあきらか。F(n)=∑c[i]、∑c[i]x[i]=nをみたすものをとるとき
> c’を∑c[i]’≦∑c[i]、∑c’[i]x[i]=nをみたすものがとれるゆえF(n)≦E(n)。□
> 　
> 定理 {E(n)}は非有界。
> 　
> 証明 >>256よりF(x[n]-1)≧[(n-1)/2]なのであきらか。□