편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
| 최신판 | 당신의 편집 | ||
| 11번째 줄: | 11번째 줄: | ||
== 재배열 부등식 == | == 재배열 부등식 == | ||
위 욕심쟁이 알고리즘 중에 수학적으로 항상 성립하는 경우. 자세한 내용은 아래와 같다. | 위 욕심쟁이 알고리즘 중에 수학적으로 항상 성립하는 경우. 자세한 내용은 아래와 같다. | ||
{{인용문|<math>a_1\leq a_2\leq\cdots\leq a_n</math>이고, <math>b_1\leq b_2\leq\cdots\leq b_n</math>인 임의의 <math>2n</math>개의 [[실수]]<ref>양의 실수만으로 제한되지 않는다는 점에 유의하여야 한다. 재배열 부등식은 모든 실수에 대하여 성립한다.</ref>에 대하여 <math>x_1,x_2,\cdots,x_n</math>은 <math>b_1,b_2,\cdots,b_n</math>을 적당히 재배열하여 얻은 실수들이라 하면, <br /> <math>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>a_i</math>가 모두 서로 같거나 <math>b_i</math>가 모두 서로 같을 때 성립한다.}} | {{인용문|<math>a_1\leq a_2\leq\cdots\leq a_n</math>이고, <math>b_1\leq b_2\leq\cdots\leq b_n</math>인 임의의 <math>2n</math>개의 [[실수]]<ref>양의 실수만으로 제한되지 않는다는 점에 유의하여야 한다. 재배열 부등식은 모든 실수에 대하여 성립한다.</ref>에 대하여 <math>x_1,x_2,\cdots,x_n</math>은 <math>b_1,b_2,\cdots,b_n</math>을 적당히 재배열하여 얻은 실수들이라 하면, <br/> <math>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>a_i</math>가 모두 서로 같거나 <math>b_i</math>가 모두 서로 같을 때 성립한다.}} | ||
증명 | 증명 | ||
<math>r< s</math>라 가정하자. 두 합 <math>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>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>r< s</math>이므로, <math>a_r< a_s,\,b_r< b_s</math>가 성립하고, 곧 <math>S-S'> 0</math>이다. 즉, 임의의 두 항을 바꾸면 합은 작아진다. 이를 일반화 시키면 <math>a_1x_1+a_2x_2+\cdots+a_nx_n\leq a_1b_1+a_2b_2+\cdots+a_nb_n</math>, (<math>\left\{x_n\right\}_{k=1}^n</math>은 수열 <math>\left\{b_n\right\}_{k=1}^n</math>의 재배열)이 성립한다. <br /> 최솟값의 경우에도 같은 방법으로 증명이 가능하다. | <math>r< s</math>라 가정하자. 두 합 <math>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>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>r< s</math>이므로, <math>a_r< a_s,\,b_r< b_s</math>가 성립하고, 곧 <math>S-S'> 0</math>이다. 즉, 임의의 두 항을 바꾸면 합은 작아진다. 이를 일반화 시키면 <math>a_1x_1+a_2x_2+\cdots+a_nx_n\leq a_1b_1+a_2b_2+\cdots+a_nb_n</math>, (<math>\left\{x_n\right\}_{k=1}^n</math>은 수열 <math>\left\{b_n\right\}_{k=1}^n</math>의 재배열)이 성립한다. <br/> 최솟값의 경우에도 같은 방법으로 증명이 가능하다. | ||
참고로 등호는 <math>S-S'=\left(a_r-a_s\right)\left(b_r-b_s\right)</math>에서 <math>a_r=a_s</math>이거나 <math>b_r=b_s</math>일 때 성립한다. 그런데 <math>r,s</math>는 고정된 두 쌍이었으므로 일반적인 경우에<math>S=S'</math>이기 위해서는 임의의 두 쌍이 서로 같아야한다. 이는 곧, 모든 <math>a_i</math>가 서로 같거나 모든 <math>b_i</math>가 서로 같을 때임을 의미한다. | 참고로 등호는 <math>S-S'=\left(a_r-a_s\right)\left(b_r-b_s\right)</math>에서 <math>a_r=a_s</math>이거나 <math>b_r=b_s</math>일 때 성립한다. 그런데 <math>r,s</math>는 고정된 두 쌍이었으므로 일반적인 경우에<math>S=S'</math>이기 위해서는 임의의 두 쌍이 서로 같아야한다. 이는 곧, 모든 <math>a_i</math>가 서로 같거나 모든 <math>b_i</math>가 서로 같을 때임을 의미한다. | ||
| 23번째 줄: | 23번째 줄: | ||
증명 | 증명 | ||
{{인용문2|재배열 부등식에 의해 아래 <math>n</math>개의 부등식이 성립한다. <br /> <math>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> <br /> <math>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> <br /> <math>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> <br /> <math>\vdots</math> <br /> <math>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> <br /> 위 부등식을 전부 더하면 구하고자 하는 [[부등식]]이 증명된다.}} | {{인용문2|재배열 부등식에 의해 아래 <math>n</math>개의 부등식이 성립한다. <br/> <math>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> <br/> <math>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> <br/> <math>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> <br/> <math>\vdots</math> <br/> <math>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> <br/> 위 부등식을 전부 더하면 구하고자 하는 [[부등식]]이 증명된다.}} | ||
== 예시 == | == 예시 == | ||