| こんにちは。 初投稿です、はじめまして。
問題ではなくて、 数列を割ったあまりの性質に関してです。
「一般に、a_1=a a_2=b a_n+2=p*a_n+1 + q*a_n (a b p q は整数)ではじまる数列a_nに対し、a_nをmで割ったあまりは、 第m^2+2項までを調べれば必ず繰り返す。
証明 a_nをmで割ったあまりをa'_nとする a'_nのとりえる値はm通りだから、 (a'_1, a'_2), (a'_2, a'_3), …, (a'_m^2+1, a'_m^2+2) のm^2+1組の中に、(a'_c, a'_c+1) = (a'_d, a'_d+1) となる組が存在する
この証明に関して質問なんですが、 mで割ったあまりなのでm通りっていうのは分ります。 しかし、次の、 (a'_1, a'_2), (a'_2, a'_3), …, (a'_m^2+1, a'_m^2+2) の (a'_m^2+1, a'_m^2+2) はどこからでてきたのでしょうか。
また、m^2+1組の中に、(a'_c, a'_c+1) = (a'_d, a'_d+1)となる組が存在する っていうところですが、 m通りしかないのにm^2+1組を調べるのがよく分りません。 よろしくお願いします。
|
No.6374 - 2011/07/30(Sat) 12:33:08
| ☆ Re: 数列のあまりの性質 / 河童 ♂ [中国] [塾講師] | | | | WAWAさん、はじめまして。 暑くて眠れない河童です。
この数列は3項間漸化式によって定まりますので、 ある項の(mで割った)余りは前の2項の影響を受けますね。
例えば、第1項の余りが a で(もちろん a が mより大きければまだ割れますが)、 第2項の余りが b なのですから、 第3項の余りは、q a + p b ということになりますよね。
思い切って、もっと具体的に言えば、 第1項を 5 で割った余りが 3 で、第2項を 5 で割った余りが 1 ならば、 第3項を 5 で割った余りは(p, q がともに1だとすると)4ということになりますね。
前の2項の余りの組合せが同じになったときに初めて、 次の項との余りの組合せ、つまり、
( a'_c , a'_c+1 , a'_c+2 ) という3つの項の余りと ( a'_d , a'_d+1 , a'_d+2 ) という3つの項の余りとが同じになるわけです。
そこから循環が始まるわけですね。 こうなると、何故 m^2 という数が出てくるのかが分かるのではないですか? 考えてみてください。 また、何故そのあとに +1 があるのか、なのですが、 たとえば、5つの可能性があるものに対して、5つを調べても「同じものがあるとは限りません」。 6つのものを調べて、初めて、「必ず同じものが見つかる」わけですね。
|
No.6375 - 2011/07/31(Sun) 05:08:45 |
| ☆ Re: 数列のあまりの性質 / WAWA ♂ [関東] [高校3年生] | | | | はじめまして、 返信ありがとうございます。 僕は地震で目覚めてしまいました…
2項の余りが連続して、ドコかのペアと同じであれば、 3項目以降は繰り返すのは理解できました。
余りはm通りなので、そのペアは、 (○ , △)として、○がm通り、△もm通りで m*m=m^2ってことでしょうか。
たとえば、2で割るとして、あまりは0か1で、 (0. 0) (0. 1) (1. 0) (1. 1) のペアがあって 上のような場合が「最高」で、最高でも4組しか存在しえないので 5組まで調べれば絶対に上の4つの中のどれかが出るってわけですね。
そして、「第m^2+2項までを調べれば必ず繰り返す。」っていうのは、 m^2+1項までに1つの同じ組が見つかって、 それをa_n+1 a_nとすれば、a_n+2、つまり第m^2+2項以降は繰り返しって 考え方であってますか。
よろしくお願いします。
|
No.6377 - 2011/07/31(Sun) 11:39:03 |
| ☆ Re: 数列のあまりの性質 / 河童 ♂ [中国] [塾講師] | | | | WAWAさん、こんばんは。 そちらは地震でたいへんですね。 十分お気を付けください。
さて、本題ですが、ほぼパーフェクトな理解ですね。素晴らしい!
最後の
> そして、「第m^2+2項までを調べれば必ず繰り返す。」っていうのは、 > m^2+1項までに1つの同じ組が見つかって、 > それをa_n+1 a_nとすれば、a_n+2、つまり第m^2+2項以降は繰り返しって > 考え方であってますか。
ここの部分が1項だけずれているかも知れません。 それから、赤文字にした部分がちょっと引っかかります。 もしかしたら、WAWAさんも以下と同じ意味で書かれたのかもしれません。そのときはお許しください。
(a_1, a_2) から (a_m^2+1, a_m^2+2) までの m^2+1 組の中に同じものが現れますので、 仮にこの2組が同じものだとすると(一番遅く同じものが見つかるというケースですね)、 a_1 , a_2 , a_3 という数の並びと a_m^2+1 , a_m^2+2 , a_m^2+3 という数の並びが同じになるわけですね。 ですから、いくら遅くとも、a_m^2+1 から循環が始まります。 ただし、a_m^2+2 まで見ないと 『どのように循環するか』 分からないということですね。 もちろん、場合によっては、すぐに循環が始まる場合もあって、 a_4 からいきなり循環が始まるかもしれません。 どちらにしても、a_m^2+2 まで見てやればOKだよ、という意味ですね。
まあ、最後の方の1つや2つの項の違いはご愛嬌で、もし2次試験ならば十分100点に近い答案だと思います。 理解できているかどうかは採点者がしっかり見てくれるでしょうからね^^
|
No.6379 - 2011/07/31(Sun) 22:25:15 |
| ☆ Re: 数列のあまりの性質 / WAWA ♂ [関東] [高校3年生] | | | | こんばんは。 返信ありがとうございます。
1項ずれて考えていました。 しかし、おかげさまで完全に理解できました!
ありがとうごいまいた。 また分らないことがあったときに、 質問させていただくかもしれません。
|
No.6380 - 2011/08/01(Mon) 01:30:27 |
|