Posts Tagged ‘ Newton’s inequality ’

2005 KMO 여름학교 모의고사 2차 #5

예전에 매쓰링크의 블로그에다 썼던 글을 번역. 처음이자 마지막으로 계절학교 조교를 했던 2005년 여름학교에서 모의고사 용으로 두 문제를 만들어 한 문제는 중등부 2차 1번, 한 문제는 고등부 2차 5번에 냈는데 둘 다 학생 총점이 14점을 넘기지 못한 일화가 있다. 이 사실을 발견한 것은 고등학교 재학 중이던 2004년이었는데 당시엔 풀지 못했다가 후에 풀이를 발견하여 문제화하였다.

가끔 대칭 부등식을 풀 때에 주어진 변수들의 symmetric sum, 즉 대칭 합을 이용하여 식을 표현하는 것이 유용한 경우가 있다. 이는 항상 가능한 일로, 대칭 식은 반드시 “기본적인” 대칭 합들로 표현이 가능하기 때문이다. 여기에서 일컫는 대칭 합은 S_{i}=\frac{t_{n-i}}{\binom{n}{i}}으로 여기서 t_{k}(x+x_{1})(x+x_{2})\cdots(x+x_{m})에서의 x^{k}의 계수이다.

이 대칭 합들에 관한 유명한 부등식 두 개가 알려져있다.
Newton’s inequality 1 \leq k \leq m-1이면 S_{k}^{2}\geq S_{k+1}S_{k-1}가 성립한다.
Maclaurin’s inequality 0 \leq a< b \leq m이면 S_{a}^{b}\geq S_{b}^{a}가 성립한다.
Maclausin의 부등식은 산술기하 평균 부등식의 일반화이기도 하다. (a=1,b=n)

이제 이 부등식들을 하나의 부등식으로 일반화를 하자. 이를 위해 볼록성과 majorization과 연관된 강력한 부등식인 Karamata’s inequality (혹은 majorization inequality) 를 이용한다.
Majorization inequality 만약 구간 I 내에서 (a_{1},\cdots,a_{n})(b_{1},\cdots,b_{n})를 majorize하면 I에서 볼록인 함수 f에 대해 \sum_{i=1}^{n}f(a_{i}) \geq \sum_{i=1}^{n}f(b_{i})가 성립한다.
이 부등식의 증명의 주요 키 포인트는 아벨 합을 이용하는 것이다. 이에 대한 증명은 Mathlinks에서도 찾아볼 수 있다. (후에 한 번 글을 올릴까 한다.)

이제 만약 \ln{S_i}들이 마치 “볼록”하거나 “오목”한 것처럼 행동한다면 비슷한 결과를 얻을 수 있어야 한다. 실제로 majorization inequality의 증명은 구간 I의 연속적인 값들을 이용하는 것이 아닌 이산적인 값들을 이용하기 때문에 비록 S_i의 “변수” i가 이산적이어도 비슷하게 적용하는 것이 가능하다. 따라서 \ln{S_i}들이 볼록한지 오목한지만 확인하면 되는데, 이것은 Newton 부등식의 직접적인 결과이다. 왜냐면 Newton 부등식 자체가
2ln S_{k}\geq ln S_{k+1}+ln S_{k=1}, 즉 \ln{S_i}의 오목성을 뜻하기 때문이다. 따라서, 우리는 다음과 같은 부등식을 얻는다.

0 이상 m 이하인 정수 a_{i},b_{i}에 대해 만약 (a_{1},a_{2},\cdots,a_{n})(b_{1},b_{2},\cdots,b_{n})을 majorize하면 \prod_{i=1}^{n}S_{a_{i}}\leq \prod_{i=1}^{n}S_{b_{i}}가 성립한다.

왜 이것이 앞의 두 부등식의 일반화일까? 이유는 간단하다. (k+1,k-1)(k,k)를 majorize하는 것에서 Newton’s inequality를 얻을 수 있고, a < b일 때 (b,b,\cdots,b,0,\cdots,0)(a,a,\cdots,a)를 majorize한다는 것에서 Maclaurin’s inequality를 얻을 수 있기 때문이다.

등호조건을 따지는 것은 그리 어렵지 않으니 직접 확인해보길 바란다. (딱히 우리의 예상을 빗나가진 않는다.)