人気ブログランキング |

カテゴリ:モチーフについて( 1269 )

練習問題1なんですが「左辺=(C∩A')∪(C∩B')」ではなく「左辺=(C∩A')∩(C∩B')」が正しいです。

おまけ。P35の問題8の回答の上から9行目、「P(A)のそれぞのれ元」と書いてありますがこれは「P(A)のそれぞれの元」でしょう。

d0164691_22110486.jpg


あり得る組み合わせを書き出して、そのなかから条件に合致するものをピックアップする。下の表がそれだ。Tと書かれているものが条件を満たす組み合わせなので、Dが1の場合を数えればいい。


d0164691_22112895.png


A=1を仮定する。

Aの発言C=1はFでB=2がT

Bの発言C=2はFでD=3がT

Cの発言D=4はFでA=2がT、すると仮定に反するので、Aは1ではない。


B=1を仮定する。

A (C=1)=F (B=2)=T

仮定に反するのでB=1ではない。


C=1を仮定する。

A (C=1)=T (B=2)=F

B (C=2)=F (D=3)=T

C (D=4)=F (A=2)=T

順番に並べると、C,A,D,Bで、矛盾はない。


D=1を仮定する。

A (C=1)=F (B=2)=T

B (C=2)=F (D=3)=T

仮定に反するのでD=1ではない。


ゆえに、C=1の仮定が正しい。


d0164691_22121392.jpg


mの行の数列の階差数列をkmと書きましょう。mの行の数列am(n)と変数nを合わせるために、階差数列の項には0.5を足します。

km(1.5)=m+1

km(n+0.5)=2*km(n-0.5)


mの行の数列そのものは

am(1)=m

am(n)=am(n-1)+km(n-0.5)


暑い日に計算したのであっているのか不安だ。


前回の数表をあらためて見てみます。

たんぽぽさんに指摘されたのですが、横の数列の階差数列が等比数列になっています。2の行を書き出して、その下に階差数列を書きます。


2 5 11 23 47 95

3 6 12 24 48


階差数列は初項が3で公比が2です、つまり倍々に増えています。

同様に3の行を見てみましょう。


3 7 15 31 63 127

4 8 16 32 64


階差数列の初項は4、公比が2です、つまり倍々に増えています。

mの行は定義より初項がmで、階差数列の初項がm+1、公比が2と仮定できます。


d0164691_12443116.png



任意の正の整数は異なるフィボナッチ数の和として書けるか?
任意の正の整数は異なるリュカ数の和として書けるか?

いままで連載してきた上記命題について、念のために背理法での証明を示しておきます。

背理法

すべての時点でnl≠Lnmとします。これはnaから無限に有限の数を引けるか(1)、あるいはどこかの時点で、初めてnm=nl-Lnm<0となること(2)、を意味します。

(1)はそもそもありえません。
(2)は、nlよりも小さい、最大のリュカ数がLnmなので矛盾しています。また最小のリュカ数は1なのでnlは0以下になります。すると「初めてnm=nl-Lnm<0となる」に矛盾します。



リュカ数は2,1,3,4,7,11,18・・と続く数列で、フィボナッチ数列の初項を2にしたものです。

となりあうリュカ数の比はフィボナッチ数列と同じく、ほぼ黄金比です。なので、1以外のあるリュカ数Lkを二倍にしたらL(k+1)よりも大きくなります。以下、昨日までのフィボナッチ数と同じ議論です。

任意の正の整数naから、naよりも小さい、最大のリュカ数Lnaを引いた差をnbとします。nb=0ならばna=Lnaです。nbがゼロでなければ、nbから、nbよりも小さい、最大のリュカ数Lnbを引いた差をncとします。以下、同じことを繰り返します。

naは有限の数なのである時点でnl=Lnmになります。このときna=Lna+Lnb+・・Lnmです。

QED



以下、naと書いてあるものはnとaの積ではなく、nの添字aです。


任意の正の整数naからna以下で一番大きいフィボナッチ数Fnaを引いて、残りをnbとする。nbはFnaよりも小さい。nbが0であればna=Fnaとなる。


nb≠0のときに、nbからnb以下で一番大きいフィボナッチ数Fnbを引いて、残りをncとする。nc=0ならば・・と続ける。


naは有限の数なので、どこかの時点で残りの数nlからフィボナッチ数Fnlを引いた残りnm=0になる。すると、na=Fna+Fnb+・・Fnlとなる。そしてこれは一意に決まる。


さて、フィボナッチ数ではなくリュカ数でこの問題は成立するか? またフィボナッチ数列は負にも拡張できるのだけど、負の整数もフィボナッチ数の和で記述できるのか?




この問題は川添愛さんの「数の女王」から取りました。


隣り合うフィボナッチ数の比はほぼ黄金比である。


3以上の任意の正の整数xについて、x以下で一番大きいフィボナッチ数Fxはx/2より大きい。なので2*Fxはxより大きい。


別の言い方をすると、3以上の任意の数xから、x以下で一番大きいフィボナッチ数Fxを引いた時に残る数はFxより小さい。


続く


任意のnについて、(2^n)-1までの二進数の1/0を入れ替えると昇順と降順が入れ替わる 2

数学的帰納法でいく。0から3までの二進数をxとして、1/0を入れ替えたものを¬xとする。前にも書いたようにxと¬xは昇順と降順が入れ替わる。

つぎに0から7までの二進数を考える。0から3までは0xで、4から7までは1xである。1/0を入れ替えると、1¬x、0¬xとならぶ。これは0から7までの二進数の昇順と降順を入れ替えたものだ。

「任意のnについて、(2^n)-1までの二進数の1/0を入れ替えると昇順と降順が入れ替わる」を仮定する。(2^n)-1までの二進数をXとすると、(2^(n+1))-1までの二進数は0Xと1Xである。仮定より「Xが¬Xになる」ので、0Xと1Xは1¬Xと0¬Xになる。これは0から(2^(n+1))-1までの二進数の昇順と降順が入れ替わったものだ。

QED