|
doba |
|
以下、前の検討に従い、言い換えた問題です。
＜問題２＞ b(1)=0 b(2)=1 b(k)=|b(k+2)-b(k+1)| （k=1,2,…,n-2） b(k)≠0 （k=2,3,…,n） b(n)＞b(n-1) を満たすような有限数列{b(k)}（k=1,2,…,n）の個数を求めよ。 ただし、n≧6とする。 ＝＝＝＝＝＝＝＝＝＝＝＝＝ b(1)=|b(3)-b(2)|より b(3)=1である。 また、 b(k)=|b(k+2)-b(k+1)|であり、なおかつ、b(k)≠0であることは b(k+2)=b(k+1)+b(k)またはb(k+2)=b(k+1)-b(k)であり、 なおかつ、b(k)＞0であることと同値である。 したがって、与えられた{b(k)}が満たすべき条件は、 b(1)=0 b(2)=1 b(3)=1 b(k+2)=b(k+1)+b(k)またはb(k+2)=b(k+1)-b(k)（k=2,3,…,n-2） b(k)＞0（k=2,3,…,n-2） b(n-1)≠0，b(n)≠0 b(n)＞b(n-1) と言い換えられる。 いま、1≦m≦n-5である整数mについて、 c(1)=0 c(2)=1 c(3)=1 c(k+2)=c(k+1)+c(k)またはc(k+2)=c(k+1)-c(k)（k=2,3,…,m+1） c(k)＞0（k=2,3,…,m+3） を満たすような有限数列{c(k)}（k=1,2,…,m+3）を考え、 その総数をN(m) そのうち、c(m+3)=c(m+2)+c(m+1)であるものの個数をP(m) c(m+3)=c(m+2)-c(m+1)であるものの個数をQ(m)とする。 m=1のとき、 c(4)=c(3)+c(2)またはc(4)=c(3)-c(2)であるが、 c(2)=c(3)=1,c(4)＞0なので、 必ずc(4)=c(3)+c(2)となる よって、P(1)=1、Q(1)=0 2≦m≦n-5のとき、 もし、c(m+2)=c(m+1)+c(m)ならば、 c(m+2)＞c(m+1)＞0なので、 c(m+3)=c(m+2)+c(m+1)であっても c(m+3)=c(m+2)-c(m+1)であっても c(m+3)＞0を満たすので構わない。 もし、c(m+2)=c(m+1)-c(m)ならば、 c(m+1)＞c(m+2)＞0なので、 c(m+3)=c(m+2)+c(m+1)の場合はc(m+3)＞0を満たすが、 c(m+3)=c(m+2)-c(m+1)の場合はc(m+3)＜0となり条件に反する。 よって、 P(m)=P(m-1)+Q(m-1) Q(m)=P(m-1) Pのみについての漸化式を求めると、 P(1)=1,P(2)=1 P(m)=P(m-1)+P(m-2)（2≦m≦n-5） よって、P(m)はフィボナッチ数列の第m項F(m) Q(m)=P(m-1)=F(m-1)（2≦m≦n-5） N(m)=P(m)+Q(m)=F(m)+F(m-1)=F(m+1)（2≦m≦n-5） N(1)=P(1)+Q(1)=1=F(2) m=n-5のとき、有限数列{c(k)}（k=1,2,…,m+3）は 有限数列{b(k)}（k=1,2,…,n）の先頭からn-2項であるので、 {b(k)}から末尾２項を除いたもののバリエーションの数はN(n-5)=F(n-4) b(n-1)とb(n)が満たすべき条件は、 b(n-1)≠0，b(n)≠0 b(n)＞b(n-1) である。 ここで、b(n-2)＞0，b(n-3)＞0，b(n-2)≠b(n-3)が言えるので、 b(n-1)=b(n-2)+b(n-3)であっても、b(n-1)=b(n-2)-b(n-3)であっても b(n-1)≠0は成立する。 また、b(n-2)＞0より、 b(n)=b(n-1)+b(n-2)ならばb(n)＞b(n-1)は成立するが、 b(n)=b(n-1)-b(n-2)ならばb(n)＜b(n-1)となり、条件に反する。 したがって、b(n)≠0の条件を無視すれば、 可能な{b(k)}の数は2・F(n-4)となる。 あとは、b(n)=0となる場合を除外すればよい。 b(n)=0となる場合について考えると、 b(n-1)＜b(n)=0なので、 b(n-1)=-xとおくと、 b(n-2)=x b(n-3)=2x b(n-4)=x b(n-5)=x b(n-6)=0 となるので、 n=7で、{b(k)}=0,1,1,2,1,-1,0の場合だけであることがわかる。 以上より、求める個数は n=6またはn≧8のとき 2・F(n-4) n=7のとき 2・F(n-4)-1=3 となる。 ＝＝＝＝＝＝＝＝＝＝＝＝＝ n=7のときは、例外処理が入って、４個ではなく３個ですね。 n=5以下は次の通り n=2→１個 n=3→０個 n=4→１個 n=5→１個 それにしても、逆順にたどって分岐を数えるという発想はすばらしいですね。 |
|
6月26日（火） 1:49:00
30104 |