質問＜１３１１＞２００３／７／１５
from=受験生o.h
「数列？」

問１
　ねずみは毎月１匹あたり２匹ずつの割合で増え、猫１匹は１日につき
ねずみを７匹ずつ殺すものとする。月の初めに４８匹いたネズミが増え
ないように、毎月ｘ匹の猫を月末に１日だけ放つ。ｘの最小値はいくら
か。また、ｘがその値の時、何か月目の終わりにネズミはいなくなるか。

問２
　５文字abcdeを繰り返し用いて、同じ文字が隣り合わないようなｎ文字
の順列を作るとき、両端の文字が同じであるものは何通りできるか、
（ただし、ｎは２以上とする）

お便り２００３／７／１６
from=Tetsuya Kobayashi

(1) 第 n 月の月はじめのネズミの匹数を a_n と書くことにすると、
a_0 = 48, a_{n+1} = max{3a_n - 7x, 0} (n>=0)
となって、とりあえず a_n > 0 の場合のみを考慮することにすると、
a_n = 3^n(48-(7/2)x) + (7/2)x
となるので、48-(7/2)x ＜= 0 が必要なことがわかるでしょう。
それで上の不等式を満たす最小の x = 14 で実験してみると、
a_n = max{49 - 3^n, 0}
ですから、
a_0, a_1, a_2, a_3 > 0, a_4 = 0 がわかるでしょう。
だから答えは x = 14, (第何月目の月末) = 3 です。

(2)
仮に両端を a と固定します。
このときに、題意に示されたような文字列の総数を a_n とおくと、
a_3 = 4, a_4 = 12 であることは簡単に調べられます。
さて、n>=3 のとき、n+2 文字の文字列というのは、
(i) n+1 文字の文字列から最後の a を取り除いて、
そこにとなりの文字と異なり、a とも異なる文字を付加して、
その上で末尾に a を付加する。
もしくは、
(ii) n 文字の文字列に b, c, d, e を付加して、
その上で末尾に a を付加する。
かのいずれかですべてが構成されますから、
a_{n+2} = 3a_{n+1} + 4a_n (n>=3).
これを解けば、
a_n = (4^{n-1}-4(-1)^n)/5
となりますが、これはあくまでも両端が a の場合に限ったもので
あるので、これを 5 倍して、結局総数は
4^{n-1}-4(-1)^n
となります。