Evolton

北海道大学 2004年度 後期日程理系(後期)数学 第2問

Dを0≦x<yを満たす整数の組(x, y)のなす集合とする.
x=0であるDの要素(0, y)を「レベル0である」という.
次の操作Gを考える.

操作G: レベル0でないDの要素(x, y)から新たなDの要素(x′, y′)を作る.
ここでx′はyをxで割った余りであり,y′はxである.

この操作を(x, y)にn回繰り返してレベル0になるとき,
(x, y)は「レベルnである」という.
0以上のnに対して,レベルnのDの要素(x, y)のうち,
yが最小になるものを「レベルnの最小組」という.

(1) n=0, 1, 2について,レベルnの最小組をすべて求めよ.
それらが操作Gの繰り返しで,どのようにレベル0になるかを書け.

(2) 操作Gを1回行うことにより(a, b)が得られるようなDの要素をすべて求めよ.

(3) n≧1とする.(a, b)をレベルnの最小組とする.
(x, y)をレベルnの組とすれば,a≦xとなることをnについての数学的帰納法を用いて示せ.

(4) (3)により,各n≧1に対し,レベルnの最小組がただ1つ定まることがわかる.
この組を(an, bn)と表すとき,bn+1=an+bn,an+1=bnであることを示せ.

難易度7/ 10計算量6/ 10目安28分

整数、数列 ユークリッドの互除法、数学的帰納法、漸化式の変形

方針

操作Gはユークリッドの互除法であり、1回前の組は割り算の商を使って (b,qb+a) と表せる。(1) は低いレベルを直接たどり、(2) で一般の逆像を求める。
(3) は数学的帰納法で、レベル n の最小組 (an,bn) からレベル n+1 の候補 (bn,an+bn) を作る。任意のレベル n+1 の組は、1回操作するとレベル n の組になるので、その第2成分が bn 以上であることから第1成分の下限が出る。(4) はこの最小候補が実際に最小であることを確認して、フィボナッチ型の漸化式を得る。

解答

(1)
レベル0では x=0 だから、y が最小の組は (0,1) である。

レベル1の組は1回で (0,x) へ移る。余りが 0 となる必要があり、0<x<y のもとで y が最小なのは(1,2)⟶(0,1)である。

レベル2では、1回でレベル1の最小組へ移る最小候補を調べる。(2,3) に操作Gを行うと (1,2) になるので、(2,3)⟶(1,2)⟶(0,1)である。したがってレベル 0,1,2 の最小組は(0,1),(1,2),(2,3)である。

(2)
(x,y) に操作Gを行って (a,b) が得られるとする。定義から x=b であり、y を b で割った余りが a だから、y=qb+aと表せる。したがって逆像は(b,qb+a)である。a>0 なら q=1,2,…、a=0 なら y>b のため q=2,3,… である。

(3)
n について数学的帰納法を用いる。n=1 では最小組は (1,2) であり、任意のレベル1の組は第1成分が正の整数だから 1≦x である。

レベル n で主張が成り立つと仮定し、その最小組を (an,bn) とする。任意のレベル n+1 の組 (x,y) に操作Gを1回行い、(x,y)⟶(r,x)となったとする。(r,x) はレベル n の組である。帰納法の仮定からan≦rであり、最小組の定義から第2成分についてbn≦xである。また (2) より y=qx+r で q≧1 だから、y≧x+r≧an+bn.一方、(bn,an+bn)⟶(an,bn)であるから、(bn,an+bn) は実際にレベル n+1 であり、上の下限を達成する。よってこれがレベル n+1 の最小組で、その第1成分は bn である。さらに任意のレベル n+1 の組では bn≦x だから、帰納法の主張も成立する。

(4)
(3) の帰納段階で、レベル n+1 の最小組が(bn,an+bn)であることまで示した。したがってan+1=bn,bn+1=an+bnである。

総評

互除法を逆向きにたどる証明問題で、目安時間は28分程度。(2) の逆像表示 (b,qb+a) が全体の核で、a=0 のときだけ q≧2 になる点にも注意する。(3) は「最小組は y が最小」という定義から、第2成分の下限を使って第1成分の下限を出すのがポイントである。(4) の漸化式はフィボナッチ型で、低いレベルの (1,2),(2,3) と整合しているか確認するとよい。

Evolton Pro

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

冊子PDFで見る北大の整数の問題で問題集を作る

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