熊本大学 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問

方針

解法1

まず，分子側に小さい数，分母側に大きい数があるなら，その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$ の比較で極限を求める。

解法2

分子集合と分母集合の分離，および組合せの順序を，隣接交換による並べ替え不等式として整理する。最大値を調和数で表した後，積分比較で極限を挟む。

解答

解法1

(問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

である。

解法2

(問1)

分子には大きい2数，分母には小さい2数を置き，大きい分子を小さい分母と組ませるので

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

である。

(問2)

最大となる例として

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

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

をとる。

実際，分子側の $p$ と分母側の $q$ が $p < q$ なら，両者を交換したときの増分は

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

である。よって最大時の分子集合は ${n + 1, \dots, 2 n}$ である。

さらに $x > y, u > v$ に対して

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

だから，大きい分子と小さい分母を組ませるのが最大である。したがって

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

である。

(問3)

積分比較

lo g n ≦ H_{n} ≦ 1 + lo g n

より $H_{n} / lo g n \to 1$ である。したがって

\frac{S _{n}}{n lo g n} = (2 + \frac{1}{n}) \frac{H _{n}}{lo g n} - \frac{1}{lo g n} ⟶ 2

である。

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

問題

方針

解法1

解法2

解答

解法1

(問1)

(問2)

(問3)

解法2

(問1)

(問2)

(問3)

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