Evolton

名古屋大学 2005年度 後期日程 第2次学力試験理系（後期）数学 第4問

自然数を入力すると，1と2からなる列を表示するプログラムを考える．
このプログラムに入力する自然数と表示される列の関係は次の通りである．
　一般に，n (n≧3)を入力すると，
n−1を入力したときに表示される列の後にn−2を入力したときに表示される列をつないだ列が表示される．
つぎの各問に答えよ．

(1) 6を入力したときに表示される列を示せ．

(2) 空欄を埋めて，プログラムを完成させよ．
ただし，表示される列の長さが10000を超える場合は扱えなくてもよいとする．
また，270行のPRINT X(I);は，変数X(I)の値を表示し，改行しない命令である．

(3) n (n≧1)を入力したときに表示される列に現れる1の個数をanとするとき，
an，an+1，an+2の間に成立する関係式を求めよ．

【原資料について】　
確認できたアーカイブのTeX・JPG・PDFでは、入力1・2に対する初期列の表と、
(2)の空欄付きプログラム表が欠落している。

難易度5/ 10計算量4/ 10目安15分

数列、論証・証明　漸化式の変形、帰納的定義の利用、計算整理

方針

DB本文とローカルsource TeXの双方で，入力1・2に対する初期列と(2)の空欄付きプログラム表が欠落している。そのため(2)の空欄番号に対応する具体値は確定できない。解答では，欠落を明記したうえで，標準的な初期設定 F1=1,F2=2 と読む場合に(1)を示し，(3)は初期列の具体形に依存しない連結規則 Fn=Fn−1Fn−2 から1の個数の漸化式を導く。

解答

(1)

DB本文では，「入力する自然数と表示される列の関係は次の通りである」とあるにもかかわらず，入力1，入力2に対する初期列の表が欠けている。したがって，本文だけからは6を入力したときの列を一意には確定できない。

以下，通常の設定として F1=1,F2=2 と読む場合を示す。Fn を n を入力したときに表示される列とすると，n≧3 で Fn=Fn−1Fn−2 である。ここで右辺は，前の列の後ろに次の列をつなぐことを表す。

したがって F3=F2F1=21 であり，F4=F3F2=212 である。さらに F5=F4F3=21221 だから，F6=F5F4=21221212 である。

(2)

DB本文には空欄付きプログラム本体が含まれていない。したがって，空欄番号ごとに入る命令や数値は，この本文だけからは確定できない。

ただし，実装の考え方は次の通りである。表示される列を配列 X に保存するなら，まず入力1と入力2に対応する初期列を用意し，n≧3 では Fn−1 の各項を順に X に入れ，その後ろに Fn−2 の各項を順に入れればよい。最後に X(1),X(2),… を順にPRINTすれば，連結規則に合う列が表示される。

しかし，問題が求めている「空欄を埋める」形式の答えは，欠落しているプログラム表の行番号・変数名・空欄番号に依存する。そのため，原表なしに具体的な空欄解答を作ることはできない。

(3) an を Fn に現れる1の個数とする。n≧3 では Fn=Fn−1Fn−2 であり，列をつないでも1の個数は和になる。したがって an=an−1+an−2(n≧3) である。

添字を2つ進めると，n≧1 に対して an+2=an+1+an である。よって求める関係式は an+2=an+1+an である。

※初期列の表と空欄付きプログラム表は原資料にも欠落している．

総評

難度5、計算量4。ただし現状のDB本文では、初期列の表と空欄付きプログラム表が欠落しているため、完全な採点用解答にはできない。連結規則そのものはフィボナッチ型で、Fn=Fn−1Fn−2 から列の長さや1の個数が同じ漸化式に従うことは確認できる。標準的に F1=1,F2=2 と読めば(1)は F6=21221212 となるが、これは欠落した初期表の補完に依存する。(2)の空欄はプログラム表の具体的な行と空欄番号がなければ確定できないため、推測で埋めるべきではない。

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

出典: 名古屋大学 2005年度 後期 数学。問題文はHTML表示のために再入力・数式組版しています。