|
問題3007・・・ヤドカリさんのブログ http://blogs.yahoo.co.jp/oka_yadokary/1788366.html より Orz〜
数列 { F(n) } を、F(1)＝A, F(2)＝B, F(n＋2)＝F(n＋1)＋F(n) で定義する。
また、S(m)＝F(1)＋F(2)＋……＋F(m) とする。
F(1)＝A, F(2)＝B, F(3)＝A＋B, F(4)＝A＋2B, F(5)＝2A＋3B, F(6)＝3A＋5B,……
S(1)＝A, S(2)＝A＋B, S(3)＝2A＋2B, S(4)＝3A＋4B, S(5)＝5A＋7B, S(6)＝8A＋12B,……
となって、A,Bがどんな自然数でも S(6) は F(5) の4倍です。
では、A,Bがどんな自然数でも S(m) が F(25) の倍数であるとき、m＝？
☆ F(1)＝F(2)＝1 のとき、フィボナッチ数列、
F(1)＝1, F(2)＝3 のとき、ルーカス数列といいます。
画像：http://pics.livedoor.com/u/tiheisenn/4936449 より Orz〜
解答
一般に、A,Bがどんな自然数でも S(m) が F(n) の倍数であるとき、
x^2＝x＋1 の解を α,β(α＞β) とすると、α≒1.6 で、α＋β＝1, αβ＝−1 で、
(α−β)F(n)＝(α^(n−1)−β^(n−1))B＋(α^(n−2)−β^(n−2))A
(α−β)S(m)＝(α^(m＋1)−β^(m＋1)−α＋β)B＋(α^m−β^m)A
αβ＝−1 を利用して、
α^(n−1)(α−β)Fn＝{ α^(2n−2)＋(−1)^n }B＋{ α^(2n−4)−(−1)^n }αA
α^(m＋1)(α−β)Sm＝{ α^(2m＋2)＋(−1)^m−α^(m＋2)−α^m }B＋{ α^2m−(−1)^m }αA
以下の計算を簡単にするために書きかえると、
α^(n−1)(α−β)Fn＝α^(2n−4)α(αB＋A)＋(−1)^n(B−αA)
α^(m＋1)(α−β)Sm＝α^m(α^m−1)α(αB＋A)−{ α^m−(−1)^m }(B−αA)
よって、
α^(2n−4) ： (−1)^n＝α^m(α^m−1) ： −{ α^m−(−1)^m }
(−1)^nα^m(α^m−1)＝−α^(2n−4){ α^m−(−1)^m }
ここで、α^m−1＞0,α^m−(−1)^m＞0 だから、nは奇数で、
α^m(α^m−1)＝α^(2n−4){ α^m−(−1)^m }
mが偶数のときは、m＝2n−4。m＞0 より、n＞2。よって、nは3以上の奇数。
このとき、S(m)＝(α^(n−2)＋β^(n−2))F(n)
ここで、L(k)＝α^k＋β^k とおくと、
L(1)＝α＋β＝1, L(2)＝α^2＋β^2＝α＋1＋β＋1＝3,
L(k＋2)＝α^(k＋2)＋β^(k＋2)＝α^(k＋1)＋β^(k＋1)＋α^k＋β^k＝L(k＋1)＋L(k)
だから、Ln−2 は自然数、Sm は Fn の自然数倍になる。
mが奇数のときは、
α^m(α^m−1)＝α^(2n−4)(α^m＋1)
(α^m−α^(2n−4))(α^m−1)＝2α^(2n−4)
(α^m−1)(α^(m−2n＋4)−1)＝2
ここで、m は奇数で、m＝1 のときは 0＜α^m−1＜1、m≧3 のときは α^m−1＞2
また、α^2＝α＋1 を利用して、(α^3−1)(α−1)＝2α(α−1)＝2 だから、
m＝1, m−2n＋4＝3 または、m＝3, m−2n＋4＝1 すなわち、n＝m＝1 または n＝m＝3。
F(1)＝A, S(1)＝A, F(3)＝A＋B, S(3)＝2A＋2B で成り立つ。
まとめると、
nは3以上の奇数で m＝2n−4 または m＝n＝1 または m＝n＝3
問題では、n＝25 より、m＝46
う〜ん...難しい...^^;
ちなみに...わたしは...
F1+F2+F3+F4+F5
=2F3+F4+F5
だから、F6=F4+F5 が足されれば、
S6=2(F3+F4)+2F5=2F5+2F5=4F5
S10=4F5+F7=(F5+F6)+F8=(2F6+F5)+F9=(3F6+2F5)+F10=(5F6+3F5)
=11F5+11F6
=11F7
F11=F10+F9=2F9+F10=2(F8+F7)+(F9+F8)=2(F8+F7)+2F8+F7
=4F8+3F7
F12=F11+F10=4F8+3F7+2F8+F7
=6F8+4F7
F13=F12+F11
=10F8+7F7
F14=F13+F12
=16F8+11F7
S14=11F7+25F7+36F8=36F9
S6・・・5F5
S10・・・11F7
S14・・・36F9
予想的には...F25・・・(25-5)/2=10 から...6+4*10=46
S46
という...アバウトなものでした...Orz...
・友人Uさんのもの Orz〜
まず，a(n) = a(n-1) + a(n-2)，a(1) = a(2) = 1 より，少し調べれば，
F(n) = a(n-2) * A + a(n-1) * B
S(m) = a(m) * A + (a(m+1)) - 1) * B
となるのが分かります。ただし，a(-1) = 1，a(0) = 0 です。
そこで，任意の A，B に対して，S(m) = c * F(n), c, m, n は自然数，となるには，
a(m) = c * a(n-2) >= a(n-2)
a(m+1) = c * a(n-1) + 1
です。ここで，最初の式より m >= n-2 です。
そして，
a(m+1) = c * a(n-1) + a(-1)
a(m) = c * a(n-2) - a(0)
と書けるので，順次，辺々を引いて
a(m-1) = c * a(n-3) + a(1)
a(m-2) = c * a(n-4) - a(2)
a(m-3) = c * a(n-5) + a(3)
...
a(m-(n-3)) = c * a(1) + (-1)^(n-2) * a(n-3) = c + (-1)^(n-2) * a(n-3)
a(m-(n-2)) = c * a(0) + (-1)^(n-1) * a(n-2) = (-1)^(n-1) * a(n-2)
そこで，
n が偶数のとき，a(m-(n-2)) = - a(n-2) <= 0 で，このような m >= n-2 は存在しません
n が奇数のとき，a(m-(n-2)) = a(n-2)，c = a(m-(n-3)) + a(n-3)
n >= 5 ならば，m-(n-2) = n-2，m = 2(n-2)，c = a(n-1) + a(n-3)
n = 3 ならば，m = 2, c = 1 又は m = 3, c = 2
n = 1 ならば，m = 1, c = 1
です。まとめると，
n = 1 ならば，m = 1, c = 1
n = 3 ならば，m = 2, c = 1 又は m = 3, c = 2
n が 5 以上の奇数ならば，m = 2(n-2), c = a(n-1) + a(n-3)
n が偶数ならば，m は存在しない，
になります。
どっちも...すごい計算ね!! ^^; Orz〜
|
コメント（4）
