[math]1992年東京大学前期文系数学問題3

問題
方針
解答
解説
関連問題

問題

$p_1 = 1, p_2 = 1, p_{n+2} = p_{n+1}+p_n\ (n\geq 1)$によって定義される数列$\{p_n\}$をフィボナッチ数列といい、その一般項は$$p_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$で与えられる。必要ならばこの事実を用いて、次の問に答えよ。
各桁の数字が$0$か$1$であるような自然数の列$X_n (n=1,\ 2,\ \cdots)$を次の規則により定める。
$(i)$ $X_1 = 1$
$(ii)$ $X_n$のある桁の数字$\alpha$が$0$ならば$\alpha$を$1$で置き換え、$\alpha$が$1$ならば$\alpha$を$10$で置き換える。$X_n$の各桁ごとにこのような置き換えを行って得られる自然数を$X_{n+1}$とする。たとえば$X_1=1, X_2 = 10, X_3 = 101, X_4 = 10110, X_5 = 10110101, \cdots$となる。
$(1)$ $X_n$の桁数$\alpha_n$を求めよ。
$(2)$ $X_n$の中に$01$という数字の配列が現れる回数$b_n$を求めよ（例えば$b_1 = 0, b_2 = 0, b_3 = 1, b_4 = 1, b_5 = 3, \cdots$）。

方針

パズル的に楽しみながら解くと良いかもしれない。

解答

$(1)$ $X_n$の中の$1$の個数を$x_n$、$0$の個数を$y_n$とする。$\alpha_n = x_n+y_n$である。$0$からは$1$が、$1$からは$10$が作られるから、$$\begin{cases}x_{n+1} = x_n+y_n \\ y_{n+1} = x_n\end{cases}$$である。これより、$x_{n+2} = x_{n+1}+x_n\ (n\geq 1)$である。$x_1 = 1, x_2 = 1$だから、$x_n = p_n$となる。したがって、$y_n = p_{n-1}$であり、$p_0 = 0$と定めれば、これは$n\geq 1$で成り立つ。以上より、$\alpha_n = x_n+y_n = p_n+p_{n-1} = p_{n+1}$であるから、$\underline{\alpha_n = p_{n+1}}$となる。

$(2)$ $X_n$の左端に注目すると、これは$1, 0, 1, 0, \cdots$となり、$1$と$0$の繰り返しになる（厳密には数学的帰納法で示す）。作り方から$0$が$2$個並ぶことはなく、左端の$0$以外は、$0$の右隣には$1$が並ぶから、
$i$ $n$が奇数のときは$01$の数は$y_n$個
$(ii)$ $n$が偶数のときは$01$の数は$y_n-1$個
となる。$(1)$から$y_n = p_{n-1}$であったから、答えは
$n$が奇数のときは$\underline{p_{n-1}}$個
$n$が偶数のときは$\underline{p_{n-1}-1}$個
となる。

解説

文系で出題された問題であるが理系の試験に出しても通用したことだろう。$(1)$では補助数列の設定が必要だが、自分で気がつくことができればそれほど難しくはない。とは言っても普段から問題の誘導に乗ってばかりでは手も足も出ないということになってしまうので、自分の頭で考える訓練は継続するべきだろう。

$(2)$も発想が要求される良い問題である。$0$の右隣には必ず$1$がくるのでは？、でも一番右に$0$があるときもある、右端の数字は$1$と$0$の繰り返しだ、などというステップを登らなくてはいけないが、どこかで躓いてしまいそうである。こういった問題を解くのが楽しめれば、数学の学習はどんどん自分の力で進められるようになっていく。

東大では一時期毎年のようにフィボナッチ数列の問題が出題されていた。整数と絡めることが多いが、図形、場合の数との融合問題であることも。

問題

方針

解答

解説

関連問題

コメント