北海道大学 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つ定まることがわかる．この組を $(a_{n}, b_{n})$ と表すとき， $b_{n + 1} = a_{n} + b_{n}$ ， $a_{n + 1} = b_{n}$ であることを示せ．

出典：北海道大学 2004年度後期日程第2次学力試験後期・理系後期第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の組は $(0, y)$ であり、 $0 < y$ だから、 $y$ が最小になるものは $(0, 1)$ である。

レベル1の組は、1回の操作Gでレベル0になる組である。 $(x, y)$ から操作Gで $(0, x)$ が得られるには、 $y$ を $x$ で割った余りが $0$ でなければならない。 $0 < x < y$ なので、 $y$ を最小にするには $(x, y) = (1, 2)$ である。実際、 $(1, 2) ⟶ (0, 1)$ である。

レベル2の最小組は、1回の操作でレベル1の最小組 $(1, 2)$ へ移るもののうち、 $y$ が最小のものである。 $(x, y)$ から $(1, 2)$ が得られるには $x = 2$ 、かつ $y$ を $2$ で割った余りが $1$ でなければならない。 $y > 2$ で最小なのは $y = 3$ である。したがって $(2, 3) ⟶ (1, 2) ⟶ (0, 1)$ である。

以上より、レベル $0, 1, 2$ の最小組はそれぞれ $(0, 1), (1, 2), (2, 3)$ である。

(2)

操作Gを1回行って $(a, b)$ が得られるとする。もとの組を $(x, y)$ とすれば、操作Gの定義から $y^{'} = x = b$ である。したがって $x = b$ である。また $x^{'} = a$ は $y$ を $x = b$ で割った余りなので、ある整数 $q$ を用いて $y = q b + a$ と表される。

もとの組は $D$ の要素なので $0 ≦ b < q b + a$ でなければならない。 $(a, b) \in D$ より $0 ≦ a < b$ である。 $a > 0$ のときは $q ≧ 1$ でよく、 $a = 0$ のときは $q b > b$ が必要なので $q ≧ 2$ である。したがって求める組は $(b, q b + a)$ であり、 $a > 0 のとき q = 1, 2, 3, \dots,$ $a = 0 のとき q = 2, 3, 4, \dots$ である。

(3)

数学的帰納法で示す。 $n = 1$ のとき、レベル1の最小組は $(1, 2)$ である。任意のレベル1の組 $(x, y)$ はレベル0ではないので $x > 0$ であり、整数だから $1 ≦ x$ である。よって主張は成り立つ。

次に、レベル $n$ で主張が成り立つと仮定する。レベル $n$ の最小組を $(a_{n}, b_{n})$ とする。任意のレベル $n + 1$ の組 $(x, y)$ に操作Gを1回行うと、あるレベル $n$ の組 $(r, x)$ が得られる。ここで $(r, x)$ はレベル $n$ の組であるから、レベル $n$ の最小組の定義より、その第2成分は $x ≧ b_{n}$ である。

一方、(2) より、 $(a_{n}, b_{n})$ へ1回で移る組のうち $y$ が最小のものは $(b_{n}, a_{n} + b_{n})$ である。したがってレベル $n + 1$ の最小組の第1成分は $b_{n}$ である。上で示したように、任意のレベル $n + 1$ の組の第1成分 $x$ は $b_{n}$ 以上であるから、レベル $n + 1$ でも主張が成り立つ。

よってすべての $n ≧ 1$ について、レベル $n$ の最小組を $(a, b)$ とすると、任意のレベル $n$ の組 $(x, y)$ に対して $a ≦ x$ が成り立つ。

(4)

レベル $n$ の最小組を $(a_{n}, b_{n})$ とする。レベル $n + 1$ の組で、1回の操作により $(a_{n}, b_{n})$ へ移るものは、(2) より $(b_{n}, q b_{n} + a_{n}) (q = 1, 2, 3, \dots)$ である。このうち $y$ が最小になるのは $q = 1$ のときであり、その組は $(b_{n}, a_{n} + b_{n})$ である。

(3) により、レベル $n + 1$ の最小組の第1成分はこれより小さくなれない。また、上の組は実際にレベル $n + 1$ である。したがって $(a_{n + 1}, b_{n + 1}) = (b_{n}, a_{n} + b_{n})$ である。すなわち $a_{n + 1} = b_{n}, b_{n + 1} = a_{n} + b_{n}$ である。

北海道大学 2004年度後期・理系数学 後期 第2問

問題

方針

解答

(1)

(2)

(3)

(4)

北海道大学 2004年度
後期・理系数学後期第2問