Evolton

東京大学 1992年度 前期日程 第2次学力試験文系数学 第3問

p1=1，p2=1，pn+2=pn+pn+1 (n≧1)によって定義される数列{pn}をフィボナッチ数列といい，その一般項はpn=15{(1+52)n−(1−52)n}で与えられる。必要ならばこの事実を用いて，次の問いに答えよ。

各桁の数字が0か1であるような自然数の列Xn (n=1,2,⋯ )を次の規則により定める。

(i) X1=1

(ii) Xnのある桁の数字αが0ならばαを1で置き換え，αが1ならばαを'10'で置き換える。
Xnの各桁ごとにこのような置き換えを行って得られる自然数をXn+1とする。

たとえば，X1=1，X2=10，X3=101，X4=10110，X5=10110101，⋯となる。

(1) Xnの桁数anを求めよ。

(2) Xnの中に'01'という数字の配列が現れる回数bnを求めよ
(たとえば,b1=0,b2=0,b3=1,b4=1,b5=3,⋯ )。

難易度6/ 10計算量5/ 10目安20分

数列、場合の数　漸化式の変形、帰納的定義の利用、場合分け、計算整理

方針

置換規則をそのまま追うと，Xn+1=XnXn−1 という連結関係が得られる。これにより桁数 an はフィボナッチ型の漸化式を満たす。(2)では，0は1から作られ，この列には ′00′ が現れないことを使う。0の個数を cn とすると cn=pn−1 であり，末尾が0である偶数番だけ ′01′ を作らない0が1つある。別解として，連結 Xn+1=XnXn−1 の境目で ′01′ が増えるかを調べる漸化式でも求められる。

解答

(1)
置換規則から Xn+1=XnXn−1(n≧2) が成り立つ。実際，Xn は Xn−1 の各桁を置換して得られ，さらにその各桁を置換すると，前半に Xn，後半に Xn−1 が続く形になる。

したがって桁数 an は an+1=an+an−1(n≧2) を満たす。また a1=1,a2=2 である。フィボナッチ数列 p1=1,p2=1 と比べると an=pn+1 である。

(2)
まず Xn に含まれる0の個数を cn とする。置換で0が生じるのは，もとの桁が1のときだけである。したがって，Xn+1 に含まれる0の個数は Xn に含まれる1の個数に等しいので cn+1=an−cn である。初めの値を調べると c2=1，c3=1 であり，また cn+1=an−cn と an=pn+1 から cn=pn−1(n≧2) が成り立つ。

次に，この列には ′00′ が現れないことを確認する。置換規則では 0 は 1 に変わり，1 は ′10′ に変わるので，置換の内部で ′00′ は生じない。また連結関係 Xn+1=XnXn−1 の境目でも，末尾と先頭を見れば ′00′ は生じない。

したがって，Xn 内の0は，末尾にある場合を除いて，必ず直後に1を伴い，′01′ を1回作る。さらに Xn の末尾は，n が偶数のとき0，n が奇数のとき1である。実際，末尾は Xn−1 の末尾と交互に変わる。

よって b1=0 であり，n≧2 についてbn={pn−1(n が奇数),pn−1−1(n が偶数)である。

別解。連結関係から直接 bn の漸化式を作ってもよい。Xn+1=XnXn−1 なので，′01′ は Xn 内部のもの，Xn−1 内部のもの，そして境目でできるものに分かれる。境目で ′01′ ができるのは，Xn の末尾が0で Xn−1 の先頭が1のとき，すなわち n が偶数のときである。よってbn+1=bn+bn−1+{1(n が偶数),0(n が奇数)となる。初期値 b1=0,b2=0 から計算しても，上の式と同じ結果が得られる。

総評

0と1の置換列を，フィボナッチ型の連結構造として読む問題である。目安時間は20分。(1)は Xn+1=XnXn−1 に気づけば桁数がすぐ出る。(2)では ′01′ を直接数えるより，まず0の個数を数え，末尾が0のときだけ1つ差し引くと整理しやすい。′00′ が現れないことと，偶数番の末尾が0であることを答案中で確認するのが採点上の要点である。

冊子PDFで見る東大の数列の問題で問題集を作る

出典: 東京大学 1992年度 第2次学力試験 数学。問題文はHTML表示のために再入力・数式組版しています。