トップ› 東京工業大学› 2003年› 理系第2問

東京工業大学 2003年理系第2問解説

方針・初手

長方形から正方形を切り取った後に残る長方形の「2辺の長さの比」に注目する。操作を行う前の長方形の2辺の比が $1 : x \ (x > 1)$ であるとき、一辺の長さが $1$ の正方形を切り取ると、残る長方形の2辺の長さは $1$ と $x-1$ になる。この残った長方形について、次の3つの場合が考えられる。

$x - 1 > 1$ すなわち $x > 2$ のとき、長辺と短辺の比は $1 : (x-1)$ となる。
$0 < x - 1 < 1$ すなわち $1 < x < 2$ のとき、長辺と短辺の比は $(x-1) : 1 = 1 : \frac{1}{x-1}$ となる。
$x - 1 = 1$ すなわち $x = 2$ のとき、残った図形は正方形となり、操作が終了する。

したがって、$n$ 回の操作で終わるような比 $x$ の集合を逆算して求める方針が有効である。

解法1

長方形の2辺の長さの比を常に $1 : x \ (x > 1)$ で表す。 1回の操作によって残る長方形の2辺の比を $1 : x'$ とすると、上の考察から $x$ と $x'$ の関係は以下のようになる。

$$ x' = \begin{cases} x - 1 & (x > 2) \\ \frac{1}{x - 1} & (1 < x < 2) \end{cases} $$

また、$x = 2$ のときは残った図形が正方形となり、この1回の操作で終了する。この関係を逆算し、$x'$ から $x$ を求める式を作ると、

$$ \begin{cases} x = x' + 1 \\ x = 1 + \frac{1}{x'} \end{cases} $$

となる。ここで、$n$ 回の操作で終了するような比 $x$ の値の集合を $S_n$ とする。操作が1回で終わるのは $x = 2$ のときであるから、

$$ S_1 = \{2\} $$

である。また、$n \geqq 1$ において、$n+1$ 回の操作で終わるための条件は、1回目の操作後に残る長方形の比 $x'$ が $n$ 回で終了すること、すなわち $x' \in S_n$ となることである。したがって、集合 $S_{n+1}$ は $S_n$ の要素 $t$ を用いて次のように構成される。

$$ S_{n+1} = \left\{ t + 1 \mid t \in S_n \right\} \cup \left\{ 1 + \frac{1}{t} \mid t \in S_n \right\} $$

(1) 漸化式を用いて $S_2, S_3$ を順に求める。

$$ S_1 = \{2\} $$

$S_2$ は $t=2$ を $t+1$ および $1+\frac{1}{t}$ に代入して得られる。

$$ S_2 = \left\{ 2 + 1, 1 + \frac{1}{2} \right\} = \left\{ 3, \frac{3}{2} \right\} $$

$S_3$ は $t=3$ と $t=\frac{3}{2}$ をそれぞれ代入して得られる。 $t=3$ のとき：

$$ 3 + 1 = 4, \quad 1 + \frac{1}{3} = \frac{4}{3} $$

$t=\frac{3}{2}$ のとき：

$$ \frac{3}{2} + 1 = \frac{5}{2}, \quad 1 + \frac{1}{\frac{3}{2}} = 1 + \frac{2}{3} = \frac{5}{3} $$

よって、$3$ 回で操作が終わる $a$ の値の集合 $S_3$ は、

$$ S_3 = \left\{ 4, \frac{4}{3}, \frac{5}{2}, \frac{5}{3} \right\} $$

となり、これが求める $a$ の値である。

(2) 任意の自然数 $n$ について、$S_n$ のすべての要素が $1$ より大きいことを帰納的に示す。 $S_1 = \{2\}$ より、$n=1$ のときは成り立つ。 $S_k$ のすべての要素 $t$ が $t > 1$ を満たすと仮定すると、$t+1 > 2 > 1$ であり、$1+\frac{1}{t} > 1$ となるため、$S_{k+1}$ の要素もすべて $1$ より大きい。よって常に成り立つ。

$S_n$ の最大値を $M_n$、最小値を $m_n$ とおく。

$$ M_n = n + 1, \quad m_n = \frac{n+1}{n} $$

となることを数学的帰納法で証明する。

(i)

$n = 1$ のとき $S_1 = \{2\}$ より、$M_1 = 2 = 1+1, m_1 = 2 = \frac{1+1}{1}$ であり、成立する。

(ii)

$n = k$ ($k \geqq 1$) のとき成立すると仮定する。すなわち、$M_k = k + 1, m_k = \frac{k+1}{k}$ である。 $S_{k+1}$ の要素は $t \in S_k$ に対して $t+1$ または $1+\frac{1}{t}$ と表される。 $t$ が $m_k \leqq t \leqq M_k$ を動くとき、 $t+1$ の取り得る値の範囲は、

$$ m_k + 1 \leqq t + 1 \leqq M_k + 1 $$

であり、最大値は $M_k + 1 = k + 2$、最小値は $\frac{k+1}{k} + 1 = \frac{2k+1}{k}$ である。一方、$1+\frac{1}{t}$ は単調減少であるから、取り得る値の範囲は、

$$ 1 + \frac{1}{M_k} \leqq 1 + \frac{1}{t} \leqq 1 + \frac{1}{m_k} $$

であり、最大値は $1 + \frac{k}{k+1} = \frac{2k+1}{k+1}$、最小値は $1 + \frac{1}{k+1} = \frac{k+2}{k+1}$ である。

ここで、$k \geqq 1$ より、

$$ \frac{2k+1}{k+1} = 2 - \frac{1}{k+1} < 2 $$

であり、また

$$ k + 2 \geqq 3 $$

であるから、$1+\frac{1}{t}$ の最大値は $2$ 未満であり、$t+1$ の最大値は $3$ 以上である。したがって、$S_{k+1}$ 全体の最大値 $M_{k+1}$ は、

$$ M_{k+1} = k + 2 $$

となる。同様に、$S_{k+1}$ 全体の最小値について、

$$ \frac{2k+1}{k} = 2 + \frac{1}{k} > 2 $$

であり、また

$$ \frac{k+2}{k+1} = 1 + \frac{1}{k+1} < 2 $$

であるから、$t+1$ の最小値は $2$ より大きく、$1+\frac{1}{t}$ の最小値は $2$ 未満である。したがって、$S_{k+1}$ 全体の最小値 $m_{k+1}$ は、

$$ m_{k+1} = \frac{k+2}{k+1} $$

となる。以上より、$n = k+1$ のときも成立する。

(i), (ii) より、すべての自然数 $n$ について最大値は $n+1$、最小値は $\frac{n+1}{n}$ である。

解説

長方形から正方形を切り取る操作は、ユークリッドの互除法や連分数展開の幾何学的な意味と深く結びついている。問題の操作をそのまま追うと条件分岐が複雑になるが、「終了する状態（比が $1:1$）」から逆算していくことで、各ステップで取り得る値を漸化式的な集合として簡潔に表現できる。 (2)の最大値と最小値を求める際は、2つの生成規則 $f(t) = t+1$ と $g(t) = 1+\frac{1}{t}$ の値域が $2$ を境に分かれることに気付くのがポイントである。これにより、最大値は常に $f(t)$ 側の最大値から、最小値は常に $g(t)$ 側の最小値（すなわち分母が最大となるとき）から生成されることが証明できる。