面白い問題おしえて~な@数学板 数論20050831022232

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

253 名前:132人目の素数さん[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 名前:132人目の素数さん[] 投稿日: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 名前:132人目の素数さん[] 投稿日: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]なのであきらか。□