まどか☆マギカ第9話「そんなの、あたしが許さない」

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

例題†

• &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});をフィボナッチ数列といい，その一般項は
  
  &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\});
  
  で与えられる。この事実を用いて、次の問いに答えよ。

問題†

• 各桁の数字が0か1であるような自然数の列&mimetex(X_n\left(n=1,2,\cdots\right));を次の規則により定める．

1. &mimetex(X_1=1);
2. &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)†

• &mimetex(X_n);の桁数&mimetex(a_n);を求めよ

問題(2)†

• &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);，……)

解法†

問題(1)†

&mimetex(X_n);の中の1の数を&mimetex(I_n);，0の数を&mimetex(O_n);と置く．

問題文より

&mimetex(a_n=I_n+O_n);

である．(自明)
規則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\});

となる．
ここで，&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)†

&mimetex(b_n);とフィボナッチ数列&mimetex(p_n);をいくつか書いてみる

各&mimetex(X_n);は必ず1から始まり，&mimetex(X_{n-1});の後ろに&mimetex(X_{n-2});をつなげた形になっている．

また，先頭が必ず1であるため，&mimetex(X_{n-1});の最後が0の場合は，'01'の数がさらに1つ増える．規則より，最後の数字は0と1が交互に現れる．

よって，次式が言える

&mimetex(b_n=\left\{\begin{array}{lcl}b_{n-1}+b_{n-2}+1&:&n=odd\\b_{n-1}+b_{n-2}&:&else\end{array}); ただし&mimetex((n\ge3));

ここで，上記の式をまとめるために，数列&mimetex(c_n);を導入する．

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

これにより，&mimetex(b_n);は次式で表される．

&mimetex(b_n=b_{n-1}+b_{n-2}+c_n); ただし&mimetex((n\ge3));

一般項†

&mimetex(b_n);と&mimetex(P_n);を一つズラして表をつくってみる．

表を眺めると，&mimetex(b_n);の一般項として，次の式が浮かぶ．

&mimetex(b_n=\left\{\begin{array}{lcl}p_{n-1}-1&:&n=even\\p_{n-1}&:&else\end{array}); ただし&mimetex((n\ge2));

ここで&mimetex(c_n);を使ってさらに完結にし，

&mimetex(b_n=p_{n-1}-1+c_n); ただし&mimetex((n\ge2));

と表記する．さらに&mimetex(d_n=1-c_n);と定義して，

&mimetex(b_n=p_{n-1}-d_n); ただし&mimetex((n\ge2));

と仮定する．

n=1の時†

&mimetex(b_1=0);(定義)

n=2の時†

&mimetex(b_2=p_1-d_2=1-(1-c_n)=1-1+0=0);(成り立つ)

n=3の時†

&mimetex(b_3=p_2-d_3=1-(1-c_n)=1-1+1=1);(成り立つ)

nが成立するときのn+1†

&mimetex(b_n=p_{n-1}-d_n);かつ&mimetex(b_{n-1}=p_{n-2}-d_{n-1});の時，&mimetex(b_{n+1});は定義より以下のように表せる

&mimetex(b_{n+1}=(b_n)+(b_{n-1})+c_{n+1}=(p_{n-1}-d_n)+(p_{n-2}-d_{n-1})+c_{n+1});

&mimetex(=(p_{n-1}+p_{n-2})+(-d_n-d_{n-1}+c_{n+1})=p_n+(-d_n-d_{n-1}+c_{n+1}));

ここで，定義より，&mimetex(-d_n-d_{n-1}=-1);となるため，

&mimetex(b_{n+1}=p_n+(-d_n-d_{n-1}+c_{n+1})=p_n+(-1+c_{n+1}));

となる．また，&mimetex(d_n=1-c_n);であるため，

&mimetex(b_{n+1}=p_n+(-1+c_{n+1})=p_n+(-d_{n+1})=p_n-d_{n+1});

となる．この式は&mimetex(b_n=p_{n-1}-d_n); の&mimetex(n);を&mimetex(n+1);で置き換えた物である． よって，数学的帰納法により証明された．

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

ただし

&mimetex(b_n=p_{n-1}-d_n); &mimetex((n\ge2));

である．

コメント†

見滝原中学校の授業で出題されていた1992年の東大入試問題である．

ジャンル:数学

最新の20件