九州大学 1996年度理系数学第5問解答・解説

問題

0と1を有限個並べたものを語ということにする．語の例としては0，010，00101，100110などがある．いま2つの語 $A = 1$ ， $B = 10$ をもとにして $C_{1} = A$ ， $C_{2} = B$ ， $C_{n} = C_{n - 2} C_{n - 1} C_{n - 2}$ ， $(n ≧ 3)$ のように定める．例えば， $C_{3} = 1101$ である．次の問いに答えよ．

(1) $n ≧ 3$ のとき，語 $C_{n}$ に対して，最初，または最後の数字を1個か2個取りさると，残りは同じ語が循環して現れている．このことを数学的帰納法により示せ．

(2) 語 $C_{n}$ に現れる0の個数を $a_{n}$ とし，1の個数を $b_{n}$ とする． $n \to \infty lim \frac{a _{n}}{b _{n}}$ を求めよ．

出典：九州大学 1996年度前期日程第2次学力試験理系第5問

方針

(1) は語の具体形を帰納法で強めに示す。奇数番では $C_{n} = (110)^{r} 1$ 、偶数番では $C_{n} = (101)^{r} 10$ の形になり、奇数番は端を1個、偶数番は端を2個取り去ると、残りが同じ三文字語の循環になっていることが分かる。(2) は0と1の個数が同じ線形漸化式に従うので、初期値から明示式を出して比の極限を求める。

解答

(1)

語 $W$ を $r$ 回繰り返した語を $W^{r}$ と書く。次の形を示す。 $C_{2 m + 1} = (110)^{(4^{m} - 1) /3} 1 (m ≧ 1)$ $C_{2 m} = (101)^{2 (4^{m - 1} - 1) /3} 10 (m ≧ 1)$ である。

実際、 $m = 1$ では $C_{2} = 10 = (101)^{0} 10, C_{3} = 1101 = (110)^{1} 1$ で成り立つ。

いま $C_{2 m} = (101)^{s} 10, C_{2 m + 1} = (110)^{r} 1$ と書けているとする。ただし $s = \frac{2 ( 4 ^{m - 1} - 1 )}{3}, r = \frac{4 ^{m} - 1}{3}$ である。

まず $C_{2 m + 2} = C_{2 m} C_{2 m + 1} C_{2 m} = (101)^{s} 10 (110)^{r} 1 (101)^{s} 10$ である。中央の $10 (110)^{r} 1 = (101)^{r + 1}$ を用いると $C_{2 m + 2} = (101)^{2 s + r + 1} 10$ となる。指数は $2 s + r + 1 = \frac{4 ( 4 ^{m - 1} - 1 ) + ( 4 ^{m} - 1 ) + 3}{3} = \frac{2 ( 4 ^{m} - 1 )}{3}$ であるから、偶数番の形が次へ進む。

次に、いま得た $C_{2 m + 2} = (101)^{s^{'}} 10, s^{'} = \frac{2 ( 4 ^{m} - 1 )}{3}$ を用いると $C_{2 m + 3} = C_{2 m + 1} C_{2 m + 2} C_{2 m + 1} = (110)^{r} 1 (101)^{s^{'}} 10 (110)^{r} 1$ である。中央の $1 (101)^{s^{'}} 10 = (110)^{s^{'} + 1}$ を用いると $C_{2 m + 3} = (110)^{2 r + s^{'} + 1} 1$ となる。指数は $2 r + s^{'} + 1 = \frac{2 ( 4 ^{m} - 1 ) + 2 ( 4 ^{m} - 1 ) + 3}{3} = \frac{4 ^{m + 1} - 1}{3}$ である。よって二つの形は数学的帰納法で示された。

したがって、 $n$ が奇数のときは $C_{n} = (110)^{r} 1$ である。最後の 1 個を取り去ると $(110)^{r}$ 、最初の 1 個を取り去ると $(101)^{r}$ となり、これは三文字語 $110$ の循環した語の繰り返しである。

また、 $n$ が偶数のときは $C_{n} = (101)^{r} 10$ である。最後の 2 個を取り去ると $(101)^{r}$ 、最初の 2 個を取り去ると $(110)^{r}$ となり、これも同じ三文字語の循環した語の繰り返しである。よって題意は示された。

(2)

$C_{n} = C_{n - 2} C_{n - 1} C_{n - 2}$ であるから、0 の個数 $a_{n}$ と 1 の個数 $b_{n}$ はそれぞれ $a_{n} = a_{n - 1} + 2 a_{n - 2}, b_{n} = b_{n - 1} + 2 b_{n - 2}$ を満たす。初期値は $a_{1} = 0, a_{2} = 1, b_{1} = 1, b_{2} = 1$ である。

漸化式 $x_{n} = x_{n - 1} + 2 x_{n - 2}$ の形から、解は $2^{n}$ 型と $(- 1)^{n}$ 型の和になる。初期値を代入すると $a_{n} = \frac{1}{3} {2^{n - 1} - (- 1)^{n - 1}}$ であり、また $b_{n} = \frac{1}{3} {2^{n} + (- 1)^{n - 1}}$ である。実際、どちらも同じ漸化式を満たし、 $n = 1, 2$ の初期値にも一致する。

したがって $\frac{a _{n}}{b _{n}} = \frac{2 ^{n - 1} - ( - 1 ) ^{n - 1}}{2 ^{n} + ( - 1 ) ^{n - 1}}$ である。 $n \to \infty$ で $(- 1)^{n - 1}$ は $2^{n}$ に比べて無視できるので $n \to \infty lim \frac{a _{n}}{b _{n}} = \frac{1}{2}$ である。

九州大学 1996年度理系数学 第5問

問題

方針

解答

(1)

(2)

九州大学 1996年度
理系数学第5問