PS를 위한 수학 - 재배열 부등식

재배열 부등식 Rearrangement Inequality

$r_1 \le r_2 \le \cdots \le r_n$ 이고, $s_1 \le s_2 \le \cdots \le s_n$ 이라 하자.

그러면, 임의의 $s_1,s_2,\dots,s_n$의 순열 $t_1, t_2, \dots, t_n$ 에 대해서,

$$ \begin{aligned} &r_1s_n+r_2s_{n-1} + \cdots + r_ns_1\\ &~~~\le r_1t_1 + r_2t_2 + \cdots + r_nt_n\\ &~~~\le r_1s_1 + r_2s_2 + \cdots + r_ns_n \end{aligned} $$

이 성립한다.

증명

$$ \begin{aligned} x_1 < x_2 < \dots < x_p < x_q\\ y_1 < y_2 < \dots < y_p < y_q \end{aligned} $$

일 때, $(p < q)$

$$ \begin{aligned} S_1 &= x_1y_1+x_2y_2 + \cdots + x_py_p + x_qy_q\\ S_2 &= x_1y_1 + x_2y_2 + \cdots + x_qy_q + x_py_q\\\\ S_1-S_2&=x_py_p+x_qy_q-x_qy_p-x_py_q\\ &=(x_o-x_q)(y_p-y_q)>0\\ \\ &\therefore S_1 > S_2 \end{aligned} $$

즉, 임의의 두 위치를 바꾸었을 때 합이 항상 작아지므로 최대합 $S$는 치환 $\pi$가 $\pi(i)=i$ 일 때 성립한다. $\square$

재배열 부등식은 그리디 알고리즘의 한 종류라고 볼 수 있다.

체비셰프 합 부등식 Chebyshev’s Inequality

$$ \begin{aligned} x_1 < x_2 &< \dots < x_n\\ y_1 < y_2 &< \dots < y_n\\ \Downarrow\\ n(x_1y_1+x_2y_2+\cdots + x_ny_n) &\ge (x_1 + x_2 + \cdots + x_n)(y_1 + y_2 + \cdots + y_n) \end{aligned} $$

연습 문제

BOJ 1026 - 보물

재배열 부등식의 성질을 이용해 바로 풀 수 있다. 그리디 알고리즘 문제이다.