[ 掲示板に戻る ]
記事No.46914に関するスレッドです
★ 数当て / 微積マン壱号
この問題の解き方を教えてください。
No.46914 - 2017/11/21(Tue) 16:04:25
☆ Re: 数当て / angel
色々工夫する余地はあるのですが取り敢えず。

　数列x[n]: 1,0,1,1,2,3,5,8,13,…
　数列y[n]: 0,1,1,2,3,5,8,13,21,…

という、フィボナッチ数列と同じ漸化式の数列 x[n],y[n] があったとき、

　x[1]=1, x[2]=0, x[n+2]=x[n+1]+x[n]
　y[1]=0, y[2]=1, y[n+2]=y[n+1]+y[n]
　※実際は y[n]=x[n+1] とまとめられる

数列 A[n] は

　A[n]=( (px[n]+qy[n])を10で割った余り )

と表されます。そして、「10で割った余り」で取り得る値が有限のため、これは一定周期でループします。

…ということで、x[n],y[n]を10で割った余りを書き出して周期性を調べましょう、という話になるのですが。

ただ、周期60なので本当に元に戻るまで調べるのは大変です。そこをどう工夫して早めに周期を見切るか、です。
多くとも15毎で区切ってやればなんとかはなるはずです。
No.46916 - 2017/11/21(Tue) 16:59:32
☆ Re: 数当て / らすかる
xを2で割った余りをb(x)と書くことにすると
b(A[1])=b(p)
b(A[2])=b(q)
b(A[3])=b(p+q)
b(A[4])=b(p+2q)=b(p)=b(A[1])
b(A[5])=b(2p+q)=b(q)=b(A[2])
よってb(A[n])は周期3項(以下)でループし、
b(A[3k])=b(p+q)
b(A[3k+1])=b(p)
b(A[3k+2])=b(q)
となる。
xを5で割った余りをc(x)と書くことにすると
c(A[1])=c(p)
c(A[2])=c(q)
c(A[3])=c(p+q)
c(A[4])=c(p+2q)
c(A[5])=c(2p+3q)
c(A[6])=c(3p+5q)=c(3p)
c(A[7])=c(5p+3q)=c(3q)
c(A[8])=c(3p+3q)
c(A[9])=c(3p+6q)=c(3p+q)
c(A[10])=c(6p+4q)=c(p+4q)
c(A[11])=c(4p+5q)=c(4p)
c(A[12])=c(5p+4q)=c(4q)
c(A[13])=c(4p+4q)
c(A[14])=c(4p+8q)=c(4p+3q)
c(A[15])=c(8p+7q)=c(3p+2q)
c(A[16])=c(7p+5q)=c(2p)
c(A[17])=c(5p+2q)=c(2q)
c(A[18])=c(2p+2q)
c(A[19])=c(2p+4q)
c(A[20])=c(4p+6q)=c(4p+q)
c(A[21])=c(6p+5q)=c(p)=c(A[1])
c(A[22])=c(5p+q)=c(q)=c(A[2])
よってc(A[n])は周期20項(以下)でループする。

(1)
b(A[31])=b(A[1])=b(p)=b(4)=0
c(A[31])=c(A[11])=c(4p)=c(4)=4
pは2で割り切れ、4pを5で割ると4余るのでp=6

(2)
b(A[77])=b(A[2])=b(q)=b(3)=1
c(A[77])=c(A[17])=c(2q)=c(3)=3
qを2で割ると1余り、2qを5で割ると3余るのでq=9

(3)
b(A[k])=b(p), c(A[k])=c(p)が成り立つ最小のk≧3は
(3と20の最小公倍数)+1=61

(4)
b(A[m])がqと無関係に決まるmはm=3k+1
c(A[m])がqと無関係に決まるmはm=20k+1,6,11,16
よってmが15で割って1余ればよいので
求めるmはm=16,31,46
No.46930 - 2017/11/22(Wed) 00:39:54
☆ Re: 数当て / 微積マン壱号
angelさん、らすかるさん

回答ありがとうございました！
No.46952 - 2017/11/23(Thu) 23:21:04