■フィボナッチ・ゲーム(その29)

フィボナッチ数のパズルでは

Fn-1Fn-Fn-2Fn+1=(-1)^n

例えば、

21・34=13・55-1,

34・55=21・89+1がよく用いられる。これを使った銀行パズルを紹介したい。

1日目にx1ドル銀行預金する

2日目にx2ドル銀行預金する

3日目にx3=x1+x2ドル銀行預金する

4日目にx4=x2+x3ドル銀行預金する

・・・・・・・・・・・・・・・・

n日目にxnドル銀行預金する

xn→xn-1→・・・→x1,x2を求めよ。

===================================

1,1,2,3,5,8,13,21,34,55

Fn=1+(F1+F2+・・・+Fn-2)

各Fnは2つ前までの項に関係している。

x1

x2

x3=x1+x2

x4=x2+x3=x1+2x2

x5=x3+x4=2x1+3x2

x6=x4+x5=3x1+5x2

x7=F5x1+F6x2

x8=・・・・・

x9=・・・・・

x10=・・・・・

xn=Fn-2x1+Fn-1x2

xn=x1Fn-2+x2Fn-1を満たす。

ここで

Fn-1Fn-Fn-2Fn+1=(-1)^n を用いると

Fn-1Fn-Fn-2Fn+1=(-1)^n

Fn-3Fn-2-Fn-4Fn-1=(-1)^n

x1(-1)^nFn-2+x2(-1)^nFn-1=xn(-1)^n

xnFn-3Fn-2-xnFn-4Fn-1=xn(-1)^n

より

x1=(-1)^nxnFn-3

x2=-(-1)^nxnFn-4

が求まる。

===================================

しかしながら、まだ答えが得られたわけではないのである。

これによると1日目あるいは2日目の預金額は負になってしまう。

そこで、xn=x1Fn-2+x2Fn-1より、x2からFn-2の倍数を引いて、x1に

Fn-1の倍数を加えてもよいことに気づく。

xn=x1Fn-2+x2Fn-1

xn=(x1+mFn-1)Fn-2+(x2-mFn-2)Fn-1

xn=x1Fn-2+x2Fn-1+mFn-1Fn-2-mFn-2Fn-1

したがって、一般解は

x1=(-1)^nxnFn-3+mFn-1>0

x2=-(-1)^nxnFn-4-mFn-2>0

m=[-(-1)^nxnFn-4/Fn-2]が得られる。

===================================

ax-by=1において、(x0,y0)はこれを満たすものとする。

a(x0+mb)-b(y0+ma)=1

x=x0+mb

y=y0+ma

が一般解となる。

===================================

Fn=Fn-1+Fn-2,F0=0,F1=1

(Fn,Fn+1)=1

Fn-1Fn-Fn-2Fn+1=(-1)^n

Fn+1Fn-(Fn)^2=(-1)^n

Fn=1+(F1+F2+・・・+Fn-2)

F2n+1=1+(F2+F4+・・・+F2n)

Fn-1=Fn+1-Fn

F-n=-(-1)^nFn

(Fm,Fn)=F(m,n)

Fp=5^(p-1)/2 modp

===================================

Fn-1=Fn+1-Fn

F-1=1=F1

F-2=-1=-F2

F-3=2=F3

F-4=-3=-F4

F-5=5=F5

F-6=-8=-F6

F-n=-(-1)^nFn

===================================