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であることを答案中で確認するのが採点上の要点である。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

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

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