合同式

質問

高校生向けの、ご教授をお願いします。

【問題】
a_1=１、a_2=2として、一般にはa_｛n+2｝=a_｛n+1｝＋a_n、n≧１と定義する。さらに、a_nを３で割った余りをb_nとおく。b_1からb_100までの和を求めよ。

【質問１】
解説中に、「b_nを順に並べていくと、・・・， b_i，b_｛i+1｝，・・・，b_j，b_{j+1}・・・において、b_i＝b_j，b_｛i+1｝＝b_{j+1}ならば、b_{j+1}以降はb_｛i+1｝以降の繰り返しである。」とありました。

なぜ、b_i＝b_j，b_｛i+1｝＝b_{j+1}ならば、b_{j+1}以降はb_｛i+1｝以降の繰り返しになるのですか？

【質問２】
解説中に、「３で割った余りは３通りだから、３＾２＋１回以内には必ず繰り返しが現れる。」とありました。

３で割った余りは、０、１、２の３通りあることは、分かるのですが、なぜ、３＾２＋１回以内には必ず繰り返しが現れるのですか？

回答No.5

tekcycle

いや、それは解説が悪い。
だって、もし解答にそんなこと書いたら減点だもん。説明(証明)が無いって。
基本、小さな事からコツコツ積み上げていくのが数学でしょう。
医科大学やボンクラ国私立大学ならどうか判りませんが、旧帝大なんて、その辺り五月蠅いかもしれません。勘ですが。

ふうん、駿台ですか。
やりそうなことだけれど、駿台にしてもやり過ぎでしょう。
なんだかそんな辺りで格好を付けたがる予備校なのですが。
以前も東工大の青本で、a1=xx、a2＝xx,a3＝xx,....an＝xxと書いていけば良い物を、Σを使ってまとめてしまったために、綺麗な解答だけれど受験生からはまるで読み辛い、本質を見失いそうな解答を書いてました。
いやぁ、簡単なことで、それで良いと思うんだったら自分の駿台の講義でそうやればいい。ろくな説明無しに。
たぶんクビになると思うけどなぁ、そういう講師。
解らないことを数式を用いて解るようにするのが数学なんで。

私は大雑把な勉強しかしていませんから、合同式も鳩の巣も知りませんが、それでも普通に解けるんで、出題されたって全然不思議じゃないでしょうね。
だって、書き出せば良いんだから。
繰り返しが35番目に現れます、なんてのなら不親切極まりないですがね。
高校では習わない、何とかの定理の一部が入試問題となるようなことはザラでしょうし。
その定理を正確に知っていればそりゃ有利でしょうが、知らなくても解けるような配慮は、通常きちんと為されています。

お礼

定理を知らなくても解けるような論理的思考力、式を創る創造力が必要だということですね。知識を貯めこむのは前提で、その先の現場思考が大切なのかなと思いました。

助言ありがとうございました。

回答No.4

alice_44

「高校生向け」が前提なら、あからさまに
合同式を持ち出すのは、いかんでしょう。

質問１
a_n を 3 で割った商を c_n とでも置き、
a_n = 3 c_n + b_n を使って、
漸化式から a を消してみましょう。
式の両辺を 3 で割った余りを考えれば、
b_(n+2) は b_n と b_(n+1) だけで決まり、
c_n や c_(n+1) に影響されない
ことが確認できます。

(ただし、A No.2 に書かれてあるように、
c_(n+2) のほうは、b_n や b_(n+1) の
影響を受けます。)

質問２
「鳩ノ巣原理」
A No.3 の説明が、解りやすいですねえ。

お礼

回答ありがとうございます。

ｂ_n+2＝ｂ_n+1＋ｂ_n　または、ｂ_n+2＝ｂ_n+1＋ｂ_n －３であることが確認できました。

「お医者さんになろう医学部への数学」に掲載されてたので、合同式は必須問題なのかなと思っていました。Focus Goldにも掲載されていなかったし、合同式は高校生には不要なのですね。貴重な情報をありがとうございました。

回答No.3

naniwacchi

こんばんわ。
具体的に数字を書き出した方が、早いとも思いますが。

【質問１】
＞なぜ、b[i]＝b[j]，b[i+1] ＝b[j+1]ならば、b[j+1]以降はb[i+1]以降の繰り返しになるのですか？

‪#‎1さんも説明されているように‬、もとの漸化式から考えてみてください。
たとえば、b[j+2]と b[i+2]の関係はどうなりますか？

【質問２】
＞解説中に、「３で割った余りは３通りだから、３＾２＋１回以内には必ず繰り返しが現れる。」とありました。
＞３で割った余りは、０、１、２の３通りあることは、分かるのですが、
＞なぜ、３＾２＋１回以内には必ず繰り返しが現れるのですか？

質問１の結果から、「連続する 2つの数が一致すれば、それ以降の数列も一致する（繰り返しになる）」ことがわかっています。

0, 1, 2の 3種の数を連続して 2つ並べる並べ方は、3^2＝ 9とおりあります。
実際に書き出してみると、以下のようになります。
(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)

ここで、0, 1, 2を並べてできる 11項の数列を考えます。
　11項の数列＝ a, b, c, d, e, f, g, h, i, j, k

この数列には、10組の連続する 2数が含まれています。
(a,b), (b,c), (c,d), (d,e), (e,f), (f,g), (g,h), (h,i), (i,j), (j,k)

これらに上の 9とおりの組合せをあてはめてみます。
すると、少なくとも同じ組合せになる組が発生します。

「10組のカップルに、9種類のケーキを配るとき、少なくとも 2組は同じ種類のケーキを配られることになる」
ことと同じです。（「鳩の巣原理」）
となると、3^2+1回以内ではなく、3^2+2回以内ということになるのですが・・・（何かが違う）

いずれにせよ、そのくらいの有限回数で「循環」が現れるという目安が立つので、
そのくらいまで数字を書き下していけば見つけられる。ということを意味しています。

お礼

b[j+2]＝b[i+2]という関係になります。

10人に、9種類のケーキを配るとき、少なくとも 2人は同じ種類のケーキになると同じと考えるならば、3^2+1回以内でいいのでは？と思いました。

回答ありがとうございました。理解出来ました。

回答No.2

tekcycle

どこまでやってあるの？
わからないなら、ｎが1から20くらいまで、ａ_nとｂ_nについて全部書き出してみないと。まずは。
抽象的な物を抽象的に扱うのではなく、具体的にして考えることです。
いえ、東大京大の数学科でも目指していて、抽象的なまま扱えないと気が済まないのならこの限りではありませんが。

全ての自然数は、例えば3ｘ＋ｙ(ｘ,ｙは自然数)で表せますよね。
ａ_n＝3ｘ1＋ｙ1ならb_n＝ｙ1
ａ_n+1＝3ｘ2＋ｙ2ならb_n+1＝ｙ2
ａ_n+2＝3ｘ3＋ｙ3ならb_n+2＝ｙ3
で、
ａ_n+2＝ａn+1＋ａn
より、
ａ_n+2＝3ｘ2＋ｙ2＋3ｘ1＋ｙ1
　　　＝3(ｘ2＋ｘ1)＋ｙ2＋ｙ1
　　　＝3ｘ3＋ｙ3
で、例えばｙ2＋ｙ1が３未満なら、
ｙ3＝ｙ2＋ｙ1
で良いのですが、ｙ2＋ｙ1が３以上なら、
ｙ3＝ｙ2＋ｙ1－３
となるはずです。(ｙの最大値は２で２＋２＝４だからｙ1＋ｙ2の最大値は４)

という辺りは、ａ_nやｂ_nを書き出してみると気付きそうなことです。
念のために言っておくと、何もせずに、一発で気付け、閃け、知識を紐解け、という話ではありません。

３^2＋１回以内に繰り返しが現れるはずだ、と計算無しに断言する知識や能力は私にはありませんが、
上記から、ｂ_n+2＝ｂ_n+1＋ｂ_n　か、ｂ_n+2＝ｂ_n+1＋ｂ_n －３　かの何れかで、どちらにせよ、ｂ_nとｂ_n+1からｂ_n+2が判明します。
であれば、(ｂ_k,ｂ_k+1)と(ｂ_l,ｂ_l+1)とが同じであれば、ｂ_k+2とｂ_l+2も同じになり、すると、(ｂ_k+1,ｂ_k+2)から算出されるｂ_k+3と(ｂ_l+1,ｂ_l+2)から算出されるｂ_l+3も同じになり、従って以下繰り返しが現れるはずです。(これも、書き出してみれば気がつくことです。)
ｂ_nは０,１,２の何れかですから、(ｂ_n,ｂ_n+1)の順列は全部で3^2通り。(b_nが0の場合、b_n+1は０,１,２、b_nが1の場合、b_n+1は０,１,２、....とここでも具体的に考えましょう。具体的に並べた結果が3^2というだけです。)
いくらランダムに数字が出ているように見えたとしても、そのうち同じ順列がどこかに生じる、ということです。
ただし、それを説明(証明)も無しに一言で「３＾２＋１回以内には必ず繰り返す」という解説なら乱暴すぎます。

とにかく、まずは手を動かして、具体的な数字を見て考えないとダメですよ。
その見たことをどうにか文字で表現すると、その解答のようなことになるというだけで、どこかの辞書を探したりコンピューターで検索すれば、そういう有名な典型事例、知識として押さえておかなければならない事例が載っているということではありません。

お礼

詳説をありがとうございます。理解出来ました。

定理、公式があってそれを知識としておさえておくべき問題かなと勝手に思い込み、手を動かすことを怠けました。反省しています。頂いたお言葉を肝に銘じます。

「お医者さんになろう医学部への数学」を解いていたのですが、説明をして頂いたような解説はなく、３＾２＋１回以内には必ず繰り返すという記載がありました。私にはレベルが高すぎるのかもしれません。

回答No.1

Tacosan

1: b_i = b_j, b{i+1} = b_{j+1} のとき b_{i+2} と b_{j+2} の間にどのような関係がありますか?
2: 1 と鳩の巣原理.

お礼

１　b_{i+2} ＝ b_{j+2}という関係になります。
２　鳩の巣原理という概念を初めて知りました。

ありがとうございました。理解出来ました。