新1年生からの質問がありました。
チャート・レベル4問題です。
問題 文字aとbをいくつか並べた列のうちで、bが隣り合わないものだけを考える。
文字がn個並んだものを「長さnの列」と呼ぶとき
(1)長さが3の列、長さが4の列はそれぞれ何通りあるか。
(2)長さ5の列で、aで始まる列は何通りあるか。また、長さ5の列で、bで始まる列は何通りあるか。
(3)長さnの列の個数をf(n)とするとき、f(n+2)=f(n+1)+f(n)が成り立つことを示せ。
[津田塾大学]
この手の問題は、「とにかく、具体的に考える」ことです。
具体的に書き出してみましょう。
(0)として、長さ1の列、長さ2の列で考えてみましょう。
長さ1の場合。 a, b の2個ですから、f(1)=2となります。
長さ2の場合。 aa, ab, ba の3個ですから、f(2)=3となります。
(1)
長さ3の場合。 最初の一文字目は、a か b ですね。
aから始まり、あと2文字並べればよいですね。
この場合、aaa, aab, aba の3通り有ります。
bから始まる場合は、次には必ずaが来ますね。
つまり、baから始まり、あと1文字並べれば良いですね。
従って、baa, babの2通り有ります。
従って、3+2=5 より 5通りとなります。f(3)=f(2)+f(1)が成立しています
長さ4の場合。 最初の一文字目は、 a か b ですね。
aから始まり、あと3文字並べれば良いですね。
この場合、aaaa, aaab, aaba, abaa, abab の5通り有ります。
bから始まる場合は、baから始まると考え、あと2文字並べれば良いですね。
この場合、baaa, baab, baba の3通り有ります。
従って、5+3=8 より 8通りとなります。f(4)=f(3)+f(2)が成立しています
ここまでくれば、チャートの解説が理解できると思います。
では、頑張って学習を進めて下さい。
By マリオ