재배열 부등식(rearrangement inequality)은 수학에서 두 수열의 곱의 합에 관한 기본적인 부등식으로, 실수로 이루어진 두 유한 수열이 주어졌을 때 그 곱의 합이 최대가 되는 조건과 최소가 되는 조건을 설명한다. 이 부등식은 20세기 초반의 수학자들에 의해 정립되었으며, G. H. Hardy, J. E. Littlewood, G. Pólya의 저서 《Inequalities》(1952)에 체계적으로 정리되어 있다.
정의
두 수열 $x_1 \le x_2 \le \cdots \le x_n$과 $y_1 \le y_2 \le \cdots \le y_n$이 주어지고, $\sigma$가 ${1, 2, \dots, n}$의 임의의 순열(permutation)이라고 할 때, 다음 부등식이 성립한다.
$$ x_1 y_n + x_2 y_{n-1} + \cdots + x_n y_1 \le x_1 y_{\sigma(1)} + x_2 y_{\sigma(2)} + \cdots + x_n y_{\sigma(n)} \le x_1 y_1 + x_2 y_2 + \cdots + x_n y_n $$
즉, 왼쪽 변은 두 수열이 반대 순서로 짝지어졌을 때의 합(최솟값)이고, 오른쪽 변은 같은 순서로 짝지어졌을 때의 합(최댓값)이다. 임의의 순열로 짝지은 합은 이 두 값 사이에 위치한다. 등호는 모든 $x_i$가 같거나 모든 $y_i$가 같을 때 성립한다.
의미와 직관
이 부등식의 핵심은 "큰 값은 큰 값끼리, 작은 값은 작은 값끼리 짝지을 때 합이 최대가 되고, 큰 값과 작은 값을 교차하여 짝지을 때 합이 최소가 된다"는 것이다. 예를 들어, 10달러, 20달러, 100달러 지폐 더미에서 각각 3장, 5장, 7장씩 가져갈 수 있을 때 최대 이익은 100달러 7장, 20달러 5장, 10달러 3장을 가져가는 경우이며, 이는 재배열 부등식의 상한에 해당한다. 이러한 성질은 탐욕 알고리즘(greedy algorithm)의 한 예시로 이해될 수 있다.
성질
재배열 부등식은 수열의 원소들이 실수일 때 부호에 대한 제약 없이 성립한다. 이는 산술-기하 평균 부등식이나 코시-슈바르츠 부등식과 달리 양수 조건이 필요하지 않다는 점에서 차별화된다. 또한 모든 $x_i$가 서로 다르고 모든 $y_i$가 서로 다를 경우, 최댓값을 주는 순열은 항등 순열(같은 순서)뿐이며, 최솟값을 주는 순열은 역순 순열($\sigma(i) = n - i + 1$)뿐이다.
응용
재배열 부등식은 여러 중요한 부등식의 증명에 사용된다. 산술-기하 평균 부등식(AM-GM), 코시-슈바르츠 부등식(Cauchy-Schwarz inequality), 체비쇼프 합 부등식(Chebyshev's sum inequality) 등이 재배열 부등식을 통해 증명될 수 있다. 또한 수학 경시대회(한국에서는 KMO 등)에서 자주 활용되는 도구이며, 일부 고등학교 수학 문제를 해결하는 데에도 적용될 수 있다.
일반화
재배열 부등식은 세 개 이상의 수열로 확장될 수 있다. 세 수열 $0 \le x_1 \le \cdots \le x_n$, $0 \le y_1 \le \cdots \le y_n$, $0 \le z_1 \le \cdots \le z_n$에 대해서도 유사한 형태의 부등식이 성립하지만, 이 경우에는 모든 수가 음이 아닌 실수(nonnegative)라는 조건이 필요하다. 또한 연속 함수의 형태로 일반화된 버전도 존재한다.
