Rearrangement Inequality
개요[편집 | 원본 편집]
한국의 학교 수학에서는 볼 일이 없는 부등식 중 하나. KMO와 같은 경시대회 수학을 준비한다면 꼭 알아놔야 하는 부등식이며, 딱히 경시대회를 준비하지 않는다 해도 배워놔서 나쁠 건 없다. 몇몇 고등학교 수학의 부등식문제를 날로 먹을 수 있기 때문.
욕심쟁이 알고리즘[편집 | 원본 편집]
두 수열 [math]\displaystyle{ \left\{a_n\right\}_{k=1}^n,\left\{b_n\right\}_{k=1}^n }[/math]을 양의 실수의 수열이라 가정하자. 또한 수열 [math]\displaystyle{ \left\{x_n\right\}_{k=1}^n }[/math]은 수열 [math]\displaystyle{ \left\{b_n\right\}_{k=1}^n }[/math]의 순열, 즉 재배열시킨 수열이라고 하자. 그럼 [math]\displaystyle{ n! }[/math]가지의 합 [math]\displaystyle{ S=\sum_{k=1}^na_kx_k=a_1x_1+a_2x_2+\cdots+a_nx_n }[/math] 중 어느 것이 최대이고 어느 것이 최소일까? 한 예시를 통해 생각해 보자. 세 상자에 각각 천원, 만원, 오만원이 들어 있다. 각각의 상자에서 3, 4, 5장의 지폐를 가져갈 수 있을 때, 어느 상자에서 몇 장을 가져가야 이익을 최대, 혹은 최소로 할 수 있을까? 상식적으로 생각하나 아니면 직접 수학적 계산을 통해 확인하나 최대의 이익은 오만원권 5장, 만원권 4장, 천원권 3장이다. 반대로 최소의 이익은 오만원권 3장, 만원권 4장, 천원권 5장이다. 이 알고리즘을 욕심쟁이 알고리즘 (Greedy Algorithm)이라 부른다. 이 예는 단순한 수학적 예시이지만, 수학 이외의 다양한 분야에 적용될 수 있다. 알고리즘을 좀 더 추상화 시켜서 설명하자면, 작은 것은 작은 것끼리, 큰 것은 큰 것끼리 붙여놓을 때 최대, 작은 것을 큰 것이랑, 큰 것을 작은 것이랑 붙여놓을 때 최소가 된다는 것이 핵심.[1]
재배열 부등식[편집 | 원본 편집]
위 욕심쟁이 알고리즘 중에 수학적으로 항상 성립하는 경우. 자세한 내용은 아래와 같다.
“ [math]\displaystyle{ a_1\leq a_2\leq\cdots\leq a_n }[/math]이고, [math]\displaystyle{ b_1\leq b_2\leq\cdots\leq b_n }[/math]인 임의의 [math]\displaystyle{ 2n }[/math]개의 실수[2]에 대하여 [math]\displaystyle{ x_1,x_2,\cdots,x_n }[/math]은 [math]\displaystyle{ b_1,b_2,\cdots,b_n }[/math]을 적당히 재배열하여 얻은 실수들이라 하면,
[math]\displaystyle{ a_1b_n+a_2b_{n-1}+\cdots+a_nb_1\leq a_1x_1+a_2x_2+\cdots+a_nx_n\leq a_1b_1+a_2b_2+\cdots+a_nb_n }[/math]이 성립한다. 단, 등호는 [math]\displaystyle{ a_i }[/math]가 모두 서로 같거나 [math]\displaystyle{ b_i }[/math]가 모두 서로 같을 때 성립한다.“
증명
[math]\displaystyle{ r\lt s }[/math]라 가정하자. 두 합 [math]\displaystyle{ S=a_1b_1+\cdots+a_rb_r+\cdots+a_sb_s+\cdots+a_nb_n,\,S'=a_1b_1+\cdots+a_rb_s+\cdots+a_sb_r+\cdots+a_nb_n }[/math]의 크기를 비교해 보면, [math]\displaystyle{ S-S'=a_rb_r+a_sb_s-a_rb_s-a_sb_r=a_r\left(b_r-b_s\right)-a_s\left(b_r-b_s\right)=\left(a_r-a_s\right)\left(b_r-b_s\right) }[/math]이다. 여기서 [math]\displaystyle{ r\lt s }[/math]이므로, [math]\displaystyle{ a_r\lt a_s,\,b_r\lt b_s }[/math]가 성립하고, 곧 [math]\displaystyle{ S-S'\gt 0 }[/math]이다. 즉, 임의의 두 항을 바꾸면 합은 작아진다. 이를 일반화 시키면 [math]\displaystyle{ a_1x_1+a_2x_2+\cdots+a_nx_n\leq a_1b_1+a_2b_2+\cdots+a_nb_n }[/math], ([math]\displaystyle{ \left\{x_n\right\}_{k=1}^n }[/math]은 수열 [math]\displaystyle{ \left\{b_n\right\}_{k=1}^n }[/math]의 재배열)이 성립한다.
최솟값의 경우에도 같은 방법으로 증명이 가능하다.
참고로 등호는 [math]\displaystyle{ S-S'=\left(a_r-a_s\right)\left(b_r-b_s\right) }[/math]에서 [math]\displaystyle{ a_r=a_s }[/math]이거나 [math]\displaystyle{ b_r=b_s }[/math]일 때 성립한다. 그런데 [math]\displaystyle{ r,s }[/math]는 고정된 두 쌍이었으므로 일반적인 경우에[math]\displaystyle{ S=S' }[/math]이기 위해서는 임의의 두 쌍이 서로 같아야한다. 이는 곧, 모든 [math]\displaystyle{ a_i }[/math]가 서로 같거나 모든 [math]\displaystyle{ b_i }[/math]가 서로 같을 때임을 의미한다.
체비셰프 합 부등식[편집 | 원본 편집]
러시아의 수학자 파프누티 쳬비셰프가 증명한 부등식 중 하나.[3] 재배열 부등식에서 쉽게 증명할 수 있는 부등식으로, 형태도 비슷하다.
“ [math]\displaystyle{ a_1\leq a_2\leq\cdots\leq a_n }[/math]이고, [math]\displaystyle{ b_1\leq b_2\leq\cdots\leq b_n }[/math]인 임의의 [math]\displaystyle{ 2n }[/math]개의 실수에 대하여, [math]\displaystyle{ n\left(a_1b_1+a_2b_2+\cdots+a_nb_n\right)\geq\left(a_1+a_2+\cdots+a_n\right)\left(b_1+b_2+\cdots+b_n\right)\geq n\left(a_1b_n+a_2b_{n-1}+\cdots+a_nb_1\right) }[/math] “
증명
재배열 부등식에 의해 아래 [math]\displaystyle{ n }[/math]개의 부등식이 성립한다.
[math]\displaystyle{ a_1b_1+a_2b_2+\cdots+a_nb_n\geq a_1b_1+a_2b_2+\cdots+a_nb_n\geq a_1b_n+a_2b_{n-1}+\cdots+a_nb_1 }[/math]
[math]\displaystyle{ a_1b_1+a_2b_2+\cdots+a_nb_n\geq a_1b_2+a_2b_3+\cdots+a_nb_1\geq a_1b_n+a_2b_{n-1}+\cdots+a_nb_1 }[/math]
[math]\displaystyle{ a_1b_1+a_2b_2+\cdots+a_nb_n\geq a_1b_3+a_2b_4+\cdots+a_nb_2\geq a_1b_n+a_2b_{n-1}+\cdots+a_nb_1 }[/math]
[math]\displaystyle{ \vdots }[/math]
[math]\displaystyle{ a_1b_1+a_2b_2+\cdots+a_nb_n\geq a_1b_n+a_2b_{n-1}+\cdots+a_nb_1\geq a_1b_n+a_2b_{n-1}+\cdots+a_nb_1 }[/math]
위 부등식을 전부 더하면 구하고자 하는 부등식이 증명된다.
예시[편집 | 원본 편집]
1. 양의 실수 [math]\displaystyle{ a,b,c }[/math]에 대해, [math]\displaystyle{ \frac{a+b+c}{abc}\leq\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2} }[/math]이 성립한다. 왜냐하면 이 부등식은 [math]\displaystyle{ \frac{1}{a}\cdot\frac{1}{b}+\frac{1}{b}\cdot\frac{1}{c}+\frac{1}{c}\cdot\frac{1}{a}\leq\frac{1}{a}\cdot\frac{1}{a}+\frac{1}{b}\cdot\frac{1}{b}+\frac{1}{c}\cdot\frac{1}{c} }[/math]과 동치이고, 재배열 부등식에 의해 성립하기 때문.
2. 양의 실수 [math]\displaystyle{ a,b,c }[/math]에 대해, [math]\displaystyle{ \frac{a^2}{b^2}+\frac{b^2}{c^2}+\frac{c^2}{a^2}\geq\frac{b}{a}+\frac{c}{b}+\frac{a}{c} }[/math]가 성립한다. 이 부등식을 적절히 변형하면 [math]\displaystyle{ \frac{a}{b}\cdot\frac{a}{b}+\frac{b}{c}\cdot\frac{b}{c}+\frac{c}{a}\cdot\frac{c}{a}\geq\frac{a}{b}\cdot\frac{b}{c}+\frac{b}{c}\cdot\frac{c}{a}+\frac{c}{a}\cdot\frac{a}{b} }[/math]이고, 재배열 부등식에 의해 성립한다.
3. 실수 [math]\displaystyle{ a,b,c }[/math]에 대해, [math]\displaystyle{ \frac{a+b+c}{3}\geq\sqrt{\frac{a^2+b^2+c^2}{3}} }[/math]이 성립한다. 체비셰프 합 부등식에 의해 [math]\displaystyle{ 3\left(a^2+b^2+c^2\right)\geq\left(a+b+c\right)\left(a+b+c\right) }[/math]이 성립하고, 양변을 9로 나눈 뒤 제곱근을 씌워주면 된다.