재배열 부등식 알아보기

재배열 부등식이란?

$r_1 \leq r_2 \leq \cdots \leq r_n$ 이고 $s_1 \leq s_2 \leq \cdots \leq s_n$이라 하자. 임의의 $s_1, s_2, \cdots, s_n$의 순열 $t_1, t_2, \cdots , t_n$에 대해서 다음 부등식이 성립한다.

 

$ r_1s_n + \cdots + r_n s_1 \leq r_1 t_1 + \cdots + r_n t_n  \leq r_1s_1+ \cdots + r_n s_n$

 

증명

$k<m$이고 $t_k > t_m$이라 가정하면,

$(r_m -r_k)(t_k - t_m) \geq 0$이므로 $r_kt_k + r_mt_m \leq r_mt_k + r_kt_m$이다.

즉, $t_k$와 $t_m$의 위치를 바꾸면 $r_1t_1 + \cdots r_nt_n$의 값은 증가하게 된다. 이 과정을 유한번 반복하면

$r_1t_1 + \cdots + r_nt_n$의 값은 $t_1 \leq x t_n$일때 최대이다.

 

따라서 $r_1t_1 + \cdots + r_n t_n \leq r_1 s_1 + \cdots + r_n s_n$ 이다.

 

또한, 같은 방법으로 증명하면 $r_1s_n + \cdots + r_ns_1 \leq r_1t_1 + \cdots + r_nt_n$ 이다.

 

재배열 부등식 이용한 문제

서로 다른 임의의 양의 정수 $a_1, a_2, \cdots , a_n$ 일 때,

$\sum_{k=1}^n \frac{1}{k} \leq \sum_{k=1}^n \frac{a_k}{k^2}$ 이다.

 

증명

$a_1, a_2, \cdots , a_n$을 크기순서대로 재배열하여 $a_{j_1} \leq a_{j_2} \leq \cdots \leq a_{j_n}$이라 하면, $a_1 , a_2, \cdots , a_n$은 $a_{j_1} \leq a_{j_2} \leq \cdots \leq a_{j_n}$의 순열이고, $\frac{1}{1} >\frac{1}{2} > \cdots > \frac{1}{n} $ 이므로 재배열 부등식에 의해 $\sum_{k=1}^n \frac{1}{k} \leq \sum_{k=1}^n \frac{a_k}{k^2}$가 성립한다.