北大 2004年度理系（後期）数学第2問｜問題・解答・解説

方針

操作Gはユークリッドの互除法であり、1回前の組は割り算の商を使って $(b, q b + a)$ と表せる。(1) は低いレベルを直接たどり、(2) で一般の逆像を求める。
(3) は数学的帰納法で、レベル $n$ の最小組 $(a_{n}, b_{n})$ からレベル $n + 1$ の候補 $(b_{n}, a_{n} + b_{n})$ を作る。任意のレベル $n + 1$ の組は、1回操作するとレベル $n$ の組になるので、その第2成分が $b_{n}$ 以上であることから第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 = q b + a$ と表せる。したがって逆像は $(b, q b + a)$ である。 $a > 0$ なら $q = 1, 2, \dots$ 、 $a = 0$ なら $y > b$ のため $q = 2, 3, \dots$ である。

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

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

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

総評

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

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

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

方針

解答

総評

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