余りの問題（長文）

質問

a1＝1、a2＝2で、a（n＋2）＝a（n＋1）＋6anで数列｛an｝が定められているとき、a2010を10で割った余りを求めよ。

質問１：10で割った余りは必ず循環すると（実験する前に）予想はつきますか？（普通自然数の数列ならある自然数で割った余りは必ず循環しますか？）

また、実はこの式の場合は循環します。

質問２：では、この項まで調べれば確実に周期（と循環する数の組）がわかる、という項は第何項か、実験の前に予想できますか？

（あるいはそれは実験あるのみですか？）

質問意図は、この式は循環の周期が長い（anの余りをrnとおくと、r2＝r22、r3＝r23です）のでr20まで書き出しても周期が分からず、
そもそも循環しない可能性があるのではないか。また、循環するとしても、じつは途中で計算ミスしていて、本来は循環に気づいているころなのではないか。と不安になったからです。

長文かつ乱文ですが、不明な場合補足します。
教えてください！

回答No.1

tmpname · ベストアンサー

まあこの場合a(n)の一般項が計算出来ますよね、
というのはさておき：

質問1,2ですが、こう考えましょう。
10で割った余りというのは0から9までの10通りしかありませんね。
従ってa(n)を10で割った余りをb(n)とすると、
{b(n), b(n+1)}の組み合わせはどう多く見積もっても
10×10 = 100通りしかありません。
よって頑張ってb(102)まで計算すれば絶対に同じ組み合わせが
出てくるはずです（大変ですが）。
同じ組み合わせが出てくれば、後はa(n+2) = a(n+1) + 6a(n)と
いう関係式から以降b(n)は循環することは明らかです。

更に今の場合a(n+2) - a(n+1) = 6a(n)という関係式と
6と10の最大公約数は2であることから、
{b(1), b(2)}を除くと、b(n)とb(n+1)を2で割った余りは
等しいです（つまり、n≧2ではb(n)とb(n+1)は共に
奇数か共に偶数）。
今の場合b(2) = 2であるからn≧2では
b(n)は全て偶数で、つまり{b(n), b(n+1)}の組み合わせは
{b(1), b(2)}を除くとどんなに多く見積もっても25通りしか
ありません。よって頑張ってb(28)まで計算すれば同じ
組み合わせが出て来ます（それでもまだ大変ですが）。

有理数で有限小数でないものは循環小数になる、というのも、
「余りの数が限られている」とかいう手法で証明しますね。
http://okwave.jp/qa/q3971152.html

こういう類のものは一般に「Dirichletの鳩の巣論法」と呼ばれる
もので、よく使われます。
http://ja.wikipedia.org/wiki/%E9%B3%A9%E3%81%AE%E5%B7%A3%E5%8E%9F%E7%90%86

お礼

遅くなりすみません。試験で困ったら考えてみます。ありがとうございました！

回答No.2

Kules

この問題ぐらい相手が小さい（10ぐらい）じゃないと使えないかも知れませんが。

1.
今回のような、各項を足したり引いたり定数倍したりする漸化式であればこれは言えると思います。というのは、数列は何らかのルールから成り立っているので、例えばa[n」のあまりr[n]、a[n+1]の余りr[n+1]とすれば、r[n+1]とr[n]からr[n+2]はただ一つに決まります。ある時はr[n]=2、r[n]=6の時r[n+2]が8だったのに、別の時には4になるとか、そういったことは起こりません。
（足したり引いたり定数倍したりする場合なら、というのは、「10で割り切れる部分はどこまでいっても10で割り切れるから」という前提で書いています。例えば今回の問題で、a[n]/10のような項が入っていると話は変わってくると思います。）

2.まず、r[n]=0～9で、r[n+1]=0～9なので、r[n+2]を決める時のパターンは100パターンあります。
ということは、少なくとも周期は100以下です。
ただ、これだと余りに多いので、偶数・奇数といったざっくりしたくくりで考えてみます。
・r[n]が偶数、r[n+1]も偶数の時、r[n+2]は偶数
・r[n]が奇数、r[n+1]が偶数の時、r[n+2]は偶数
・r[n]が偶数、r[n+1]が奇数の時、r[n+2]は奇数
・r[n]が奇数、r[n+1]も奇数の時、r[n+2]は奇数
となります。
ただ、最初の状態を見ると、r[2]は偶数です。ということは、r[3]は偶数です。
ここから、r[n+1]が奇数になることはあり得ないとわかります。(r[n+1]が偶数ならr[n+2]も偶数→次に考えるr[n+1]も偶数)
ということは、最初を別にすれば、r[n]、r[n+1]は偶数・偶数の組み合わせにしかならないことになります。

ここから、r[n]=0,2,4,6,8、r[n+1]=0,2,4,6,8になるので、周期は最長25であることがわかります。
もう少し絞りこんでみます。
r[n]=r[n+1]=r[n+2]
となる時がないか考えます。こうなる時があるのなら、それから先は周期もへったくれもなくずっと同じ数字が続くということなので。
r[n]=0,r[n+1]=0の時r[n+2]=0
r[n]=2,r[n+1]=2の時r[n+2]=4
r[n]=4,r[n+1]=4の時r[n+2]=8
r[n]=6,r[n+1]=6の時r[n+2]=2
r[n]=8,r[n+1]=8の時r[n+2]=6
なので、（r[n],r[n+1]）=(0,0)の組み合わせは消えました。ということは周期は最長で24ですね。
これ以上絞る方法は私にはわかりません。
まあここまで来たら５×５の表を作って、縦にr[n]、横にr[n+1]を取って各マスにr[n+2]を書きこんでいき、
スタート（r[1=1,r[2]=2,r[3]=8ですから、(2,8)からスタートすればいいと思います）からマスを順番に消していき、
すでに消したマスに当たるまでが周期となります。

参考になれば幸いです。

お礼

ありがとうございます。なかなか、絞るだけで難しい感じがしますけど、考え方は他に使えそうです。ありがとうございました。