#contents

まどか☆マギカ第9話でクラスメイトが解いていた,ホワイトボード書かれていた数学の問題.「答えよ」と書かれていたので,答えてみた.

*例題 [#y1d19b65]
-&mimetex(p_1=1);,&mimetex(p_2=1);,&mimetex(p_{n+2}=p_{n+1}+p_n\left(n \ge 1\right));によって定義される数列&mimetex(\left{p_n\right});をフィボナッチ数列といい,その一般項は&br(); &br();
&mimetex(p_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}); &br(); &br();
で与えられる。この事実を用いて、次の問いに答えよ。

*問題 [#d90a5eb8]
-各桁の数字が0か1であるような自然数の列&mimetex(X_n\left(n=1,2,\cdots\right));を次の規則により定める.
+&mimetex(X_1=1);
+&mimetex(X_n);のある桁を&mimetex(\alpha);が0ならば&mimetex(\alpha);を1で置き換え,&mimetex(\alpha);が1ならば&mimetex(\alpha);を'10'で置き換える.&mimetex(X_n);の各桁ごとにこのような置き換えを行って得られる自然数を&mimetex(X_{n+1});とする.

-たとえば&mimetex(X_1=1);,&mimetex(X_2=10);,&mimetex(X_3=101);,&mimetex(X_4=10110);,&mimetex(X_5=10110101);,……となる.

**問題(1) [#l90cf3c1]
-&mimetex(X_n);の桁数&mimetex(a_n);を求めよ
**問題(2) [#ff95473d]
-&mimetex(X_n);の中に'01'という数字の配列が現れる回数&mimetex(b_n);を求めよ.
-(たとえば&mimetex(b_1=0);,&mimetex(b_2=0);,&mimetex(b_3=1);,&mimetex(b_4=1);,&mimetex(b_5=3);,……)

*解法 [#ib22b930]
**問題(1) [#f2017cd6]
&mimetex(X_n);の中の1の数を&mimetex(I_n);,0の数を&mimetex(O_n);と置く.

問題文より

&mimetex(a_n=I_n+O_n);

である.(自明)&br();
規則2より

&mimetex(\left{\begin{array}{l}I_n=I_{n-1}+O_{n-1}\\O_n=I_{n-1}\end{array});

が成り立つ.
今,&mimetex(O_{n-1});を&mimetex(I_n);で置き換えると

&mimetex(\left{\begin{array}{l}I_n=I_{n-1}+I_{n-2}\\O_n=I_{n-1}\end{array});

と変わり,&mimetex(I_n);がフィボナッチ数列と同じになる.
&mimetex(I_1=1);,&mimetex(I_2=1);より,

&mimetex(I_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\});

となる.よって,

&mimetex(O_n=I_{n-1}=p_{n-1}=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right\});

となる.&br();
ここで,&mimetex(a_n);を書き換えると,フィボナッチ数列の定義より,

&mimetex(a_n=I_n+O_n=p_n+p_{n-1}=p_{n+1});

となる.よって

&mimetex(a_n=p_{n+1}=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right\});

となる.


**問題(2) [#c039c09c]
#stub

&mimetex(b_n=b_{n-2}+b_{n-1}+c_n);

となる.ここで&mimetex(c_n);は

&mimetex(c_n=\left\{\begin{array}{ccl}1&:&n=even\\0&:&else\end{array});

よって,(to be written)

&mimetex(b_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}+1-c_n);



*コメント [#l93b0a09]
見滝原中学校の授業で出題されていた1992年の東大入試問題である.

ジャンル[[:数学]]


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS