熊本大学 2017年度理系数学第4問解答・解説

問題

$n$ は $2$ 以上の自然数とする． $1$ から $2 n$ までの自然数の順列 $a_{1}$ ， $a_{2}$ ， $\dots$ ， $a_{2 n}$ に対して，分数の和

\frac{a _{1}}{a _{n + 1}} + \frac{a _{2}}{a _{n + 2}} + \dots + \frac{a _{n}}{a _{2 n}}

を考える． $1$ から $2 n$ までの自然数のすべての順列に対してこの和がとり得る値の最大値を $S_{n}$ とする．以下の問いに答えよ．

(問1)　 $S_{2}$ を求めよ．

(問2)　 $S_{n}$ を与える順列 $a_{1}$ ， $a_{2}$ ， $\dots$ ， $a_{2 n}$ の例を $1$ つ挙げ，その理由を述べよ．

(問3)　 $lim_{n \to \infty} \frac{S _{n}}{n l o g n}$ を求めよ．

出典：熊本大学 2017年度前期理系第4問

方針

まず，分子側に小さい数，分母側に大きい数があるなら，その2数の役割を入れ替えると和が増えることを示し，最大では分子が $n + 1, \dots, 2 n$ ，分母が $1, 2, \dots, n$ であることを導く。次に，分子が大きいものほど分母が小さいものと組むと和が増えることを交換で示す。これにより $S_{n} = (2 n + 1) \sum_{k = 1}^{n} 1/ k - n$ を得て，最後は調和和と $lo g n$ の比較で極限を求める。

解答

(問1)

$n = 2$ のとき， $1, 2, 3, 4$ を用いる。最大にするには，大きい数を分子，小さい数を分母にし，さらに大きい分子を小さい分母と組にすればよい。したがって

S_{2} = \frac{4}{1} + \frac{3}{2} = \frac{11}{2}

である。

(問2)

次の順列を考える。

a_{1} = 2 n, a_{2} = 2 n - 1, \dots, a_{n} = n + 1,

a_{n + 1} = 1, a_{n + 2} = 2, \dots, a_{2 n} = n

このとき

S_{n} ≧ k = 1 \sum n \frac{2 n + 1 - k}{k}

である。

これが最大であることを示す。ある順列で，分子側にある数 $p$ と分母側にある数 $q$ が $p < q$ を満たすとする。 $p$ が分子である項を $\frac{p}{d}$ ， $q$ が分母である項を $\frac{c}{q}$ とする。 $p$ と $q$ の位置を入れ替えると，この2項は

\frac{q}{d} + \frac{c}{p}

になる。その増加分は

\frac{q - p}{d} + c (\frac{1}{p} - \frac{1}{q}) > 0

である。よって最大のとき，分子側の数はすべて分母側の数より大きい。したがって分母側は $1, 2, \dots, n$ ，分子側は $n + 1, n + 2, \dots, 2 n$ でなければならない。

次に，分子 $x > y$ が分母 $u > v$ とそれぞれ組になっているとする。この2組を入れ替えると

\frac{x}{v} + \frac{y}{u} - (\frac{x}{u} + \frac{y}{v}) = (x - y) (\frac{1}{v} - \frac{1}{u}) > 0

である。したがって最大では，大きい分子ほど小さい分母と組む。よって上に挙げた順列が $S_{n}$ を与え，

S_{n} = k = 1 \sum n \frac{2 n + 1 - k}{k} = (2 n + 1) k = 1 \sum n \frac{1}{k} - n

である。

(問3)

$H_{n} = \sum_{k = 1}^{n} \frac{1}{k}$ とおく。(問2)より

\frac{S _{n}}{n lo g n} = \frac{2 n + 1}{n} \cdot \frac{H _{n}}{lo g n} - \frac{1}{lo g n}

である。ここで $lo g$ は自然対数である。

$1/ x$ のグラフと面積を比較すると

\int_{1}^{n} \frac{d x}{x} ≦ H_{n} ≦ 1 + \int_{1}^{n} \frac{d x}{x}

であるから

1 ≦ \frac{H _{n}}{lo g n} ≦ 1 + \frac{1}{lo g n}

である。したがって

n \to \infty lim \frac{H _{n}}{lo g n} = 1

である。よって

n \to \infty lim \frac{S _{n}}{n lo g n} = 2

である。

熊本大学 2017年度理系数学 第4問

問題

方針

解答

(問1)

(問2)

(問3)

熊本大学 2017年度
理系数学第4問