トップ› 東京大学› 1995年› 理系第4問

東京大学 1995年理系第4問解説

方針・初手

関数 $f(n) = n + \frac{N}{n}$ は、$x > 0$ における実数関数 $g(x) = x + \frac{N}{x}$ とみなしたとき、$x = \sqrt{N}$ で最小値をとる関数である。 $n$ は $N$ の正の約数であるため、$n$ が $\sqrt{N}$ に最も近い値をとるときに $f(n)$ が最小となる。この性質を利用して、$N$ の約数のうち $\sqrt{N}$ の周辺にあるものを探すことで最小値を求める。

解法1

(1)

$N = 2^k$（$k$ は正の整数）のとき、$N$ の正の約数 $n$ は $n = 2^i$（$i = 0, 1, 2, \dots, k$）と表せる。これを $f(n)$ に代入すると、

$$ f(2^i) = 2^i + \frac{2^k}{2^i} = 2^i + 2^{k-i} $$

となる。相加平均と相乗平均の関係より、

$$ 2^i + 2^{k-i} \geqq 2\sqrt{2^i \cdot 2^{k-i}} = 2\sqrt{2^k} = 2 \cdot 2^{\frac{k}{2}} = 2^{\frac{k}{2}+1} $$

が成り立つ。等号成立は $2^i = 2^{k-i}$、すなわち $i = k - i$ より $i = \frac{k}{2}$ のときである。ここで、$k$ の偶奇によって場合分けを行う。

($k$ が偶数のとき)

$i = \frac{k}{2}$ は整数となり、$n = 2^{\frac{k}{2}}$ は $N$ の約数として存在する。よって、$n = 2^{\frac{k}{2}}$ のとき $f(n)$ は最小となり、その最小値は、

$$ 2^{\frac{k}{2}+1} $$

である。

($k$ が奇数のとき)

$i$ は整数であるから $i = \frac{k}{2}$ となる約数は存在しない。関数 $g(x) = x + \frac{N}{x}$ は $x = \sqrt{N}$ を境に離れるほど値が大きくなるため、$i$ が $\frac{k}{2}$ に最も近い整数のときに $f(n)$ は最小となる。 $\frac{k}{2}$ に最も近い整数は $i = \frac{k-1}{2}$ または $i = \frac{k+1}{2}$ である。 $i = \frac{k-1}{2}$ のとき、

$$ f(2^{\frac{k-1}{2}}) = 2^{\frac{k-1}{2}} + 2^{k - \frac{k-1}{2}} = 2^{\frac{k-1}{2}} + 2^{\frac{k+1}{2}} $$

となり、式を整理すると、

$$ 2^{\frac{k-1}{2}} (1 + 2^1) = 3 \cdot 2^{\frac{k-1}{2}} $$

となる。 $i = \frac{k+1}{2}$ のときも、項の順序が入れ替わるだけで同じ値となる。よって、最小値は $3 \cdot 2^{\frac{k-1}{2}}$ である。

(2)

$N = 7!$ のとき、$N = 5040$ である。実数関数 $g(x) = x + \frac{5040}{x} \ (x>0)$ は、相加平均と相乗平均の関係より $x = \sqrt{5040}$ で最小となる。 $70^2 = 4900$、$71^2 = 5041$ であるから、

$$ 70 < \sqrt{5040} < 71 $$

が成り立つ。 $n$ は $5040$ の約数であるから、$\sqrt{5040}$ に最も近い約数を探す。 $7!$ を素因数分解すると、

$$ 7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 2^4 \cdot 3^2 \cdot 5 \cdot 7 $$

となる。 $\sqrt{5040}$ に近い整数 $70$、$71$、$72$ について約数であるかを確認する。 $70 = 2 \cdot 5 \cdot 7$ であり、素因数の指数を比較すると $5040$ の約数である。 $71$ は素数であり、$5040$ は $71$ を素因数に持たないため約数ではない。 $72 = 2^3 \cdot 3^2$ であり、素因数の指数を比較すると $5040$ の約数である。ここで、$70 \times 72 = 5040$ であるから、$n=70$ と $n=72$ は $N=5040$ におけるペアの約数（$n$ と $\frac{N}{n}$）である。関数 $f(n)$ は $n$ が $\sqrt{5040}$ に近いほど小さくなるため、約数の中で $\sqrt{5040}$ に最も近い $n = 70$（または $n = 72$）のときに最小となる。このとき、最小値は、

$$ f(70) = 70 + \frac{5040}{70} = 70 + 72 = 142 $$

となる。

解説

関数 $f(n) = n + \frac{N}{n}$ の最小化は、相加平均と相乗平均の関係から $n = \sqrt{N}$ の周辺を調べるのが定石である。 (1) では変数が指数として表されるため、指数の偶奇によって中央の値が整数になるかどうかが分かれる点に注意する。 (2) では $7!$ という具体的な値に対して、$\sqrt{7!}$ の近似値を求め、その周辺の整数が $7!$ の約数となっているかを素因数分解から判定する処理が求められる。$\sqrt{5040}$ が $70$ と $71$ の間にあることに気付けば、候補を絞り込むことができ計算量を大幅に減らすことができる。