Posts Tagged ‘ 부등식 ’

2010 JMO #4

4. 양의 실수 x,y,z에 대해 다음 부등식이 성립함을 보여라.

\displaystyle \sum_{cyc} \frac{1+xy+xz}{(1+y+z)^2} \geq 1

코시-슈바르츠 부등식으로 (1+xy+xz)(1+\frac{y}{x} + \frac{z}{x}) \geq (1+y+z)^2가 성립하니까
\displaystyle \sum_{cyc} \frac{1+xy+xz}{(1+y+z)^2} \geq \sum_{cyc} \frac{1}{1+\frac{y}{x}+\frac{z}{x}} = \sum_{cyc} \frac{x}{x+y+z}=1. 끝

등호는 x=y=z=1일 때 성립한다.

2010 KMO #5

내 기억엔 이거 예전 전국 기출문제인데..

5. 양의 실수 x,y,zx+y+z=1을 만족할 때, 다음 부등식이 성립함을 보여라.
\sqrt{\frac{x}{1-x}} + \sqrt{\frac{y}{1-y}} + \sqrt{\frac{z}{1-z}} > 2

매우 단순한 차수 맞추기를 하면 \sum \sqrt{\frac{x}{y+z}} \geq 2를 증명한 후 등호가 성립되지 않음을 보이면 된다. 그런데 \sqrt{\frac{x}{y+z}} \geq \frac{2x}{x+y+z} \Leftrightarrow x+y+z \geq 2 \sqrt{x(y+z)}가 산술기하 부등식으로 성립하고 다 더하면 바로 끝. 등호가 성립하려면 x+y=z,y+z=x,z+x=y가 성립해야 하는데 양의 실수에선 그럴 수 없으므로 모순이다.

그나저나 올해는 부등식이 두 개네.. 허허

+ 만약 음 아닌 실수도 용인하되 분모만 0이 안 되게 한다면 등호조건은 존재한다. 그러면 저 등호 조건이 x+y=z or z=0으로 되기 때문에 전체 등호조건은 x=y,z=0 등이 가능하게 된다. 이렇게 x=y=z 꼴이 아닌 등호조건 때문에 어려워진 문제. 또한 이렇기 때문에 우변의 2는 최선의 값이다. 왜냐하면 양의 실수에선 x=y, z \rightarrow 0으로 만들면 좌변의 값이 2로 수렴하므로..

2010 KMO #2

2. 양의 실수 a,b,cab+bc+ca=1을 만족할 때 다음 부등식이 성립함을 보여라.
\sqrt{a^2+b^2+\frac{1}{c^2}} + \sqrt{b^2+c^2+\frac{1}{a^2}} + \sqrt{c^2+a^2+\frac{1}{b^2}} \geq \sqrt{33}

코시-슈바르츠 부등식에 의해 \displaystyle \left( \frac{(ab+bc+ca)^2}{a^2} + b^2+c^2 \right)^2 (3^2+1^2+1^2) \geq \left( 3 \frac{ab+bc+ca}{a}+b+c \right)^2이므로 \displaystyle (LHS) \geq \sum \frac{1}{\sqrt{11}}(3 \frac{ab+bc+ca}{a}+b+c)
\displaystyle = \frac{1}{\sqrt{11}}(3\frac{(ab+bc+ca)^2}{abc} + 2(a+b+c))
\displaystyle \geq \frac{1}{\sqrt{11}} 11(a+b+c) = \sqrt{11}(a+b+c) = \sqrt{11(a+b+c)^2}
\displaystyle \geq \sqrt{33(ab+bc+ca)} = \sqrt{33}, 증명끝.

등호는 a=b=c=\frac{1}{\sqrt{3}}일 때 성립한다.

2010 FKMO #1

다음은 올해 3월 27일에 있었던 KMO 최종시험, 통칭 FKMO에서 1번으로 나온 문제이다.

삼각형 ABC의 내접원이 BC,CA,AB와 접하는 점을 각각 P,Q,R이라 하자. 삼각형 ABC의 넓이를 T, 둘레의 길이를 L이라 할 때 다음 부등식이 성립함을 보여라.
\displaystyle \left( \frac{AB}{PQ} \right)^3 + \left( \frac{BC}{QR} \right)^3 + \left( \frac{CA}{RP} \right)^3 \geq \frac{2}{\sqrt{3}}\frac{L^2}{T}

먼저 BC=a,CA=b,AB=c라 할 때 QR의 길이들을 구하자. 이는 s=\frac{a+b+c}{2}이라 할 때 AQ=AR=s-a이므로 QR=2(s-a)\sin{\frac{A}{2}}이다. 여기서 x=\frac{-a+b+c}{2}, y=\frac{a-b+c}{2},z=\frac{a+b-c}{2}라 하면 \displaystyle (LHS) = \sum_{cyc} \left( \frac{y+z}{2x \sqrt{\frac{yz}{(x+y)(x+z)}}} \right)^3가 된다.

이제 산술기하 평균 부등식을 적용하면 \displaystyle (LHS) \geq 3\prod_{cyc} \left( \frac{y+z}{2x \sqrt{\frac{yz}{(x+y)(x+z)}}} \right) = 3 \frac{(y+z)^2(z+x)^2(x+y)^2}{8x^2 y^2 z^2}가 된다. 한 편, \displaystyle (RHS)=\frac{2}{\sqrt{3}}\frac{4(x+y+z)^2}{\sqrt{xyz(x+y+z)}}이므로 \displaystyle 3 \frac{(y+z)^2(z+x)^2(x+y)^2}{8x^2 y^2 z^2} \geq \frac{2}{\sqrt{3}}\frac{4(x+y+z)^2}{\sqrt{xyz(x+y+z)}}임을 보이면 된다. 이를 정리하면 \displaystyle ((y+z)(z+x)(x+y))^2 \geq \frac{64}{3\sqrt{3}}(x+y+z)^{3/2}(xyz)^{3/2}이다.

이를 증명하기 위해 \displaystyle (y+z)(z+x)(x+y) \geq \frac{8}{3} (x+y+z)(xyz)^{2/3}임을 보이자. 이는 x,y,zx^3,y^3,z^3을 대입한 후에 정리하면 \displaystyle 3\sum_{sym}x^6y^3+6x^3y^3z^3 \geq 8\sum_{cyc}x^5y^2z^2가 된다. 이를 증명하자.

산술기하 평균 부등식, 혹은 Muirhead 부등식에 의해 \displaystyle \sum_{sym}x^6y^3z^3 \geq 2\sum_{cyc}x^6y^{3/2}z^{3/2}가 성립한다. 따라서 \displaystyle 6\sum_{cyc}x^6y^{3/2}z^{3/2}+6x^3y^3z^3 \geq 8\sum_{cyc}x^5y^2z^2임을 보이면 된다. 또 x,y,zx^2,y^2,z^2를 대입한 후 정리한 다음 양변을 2x^3y^3z^3으로 나누면 \displaystyle 3\sum_{cyc}x^9+3x^3y^3z^3 \geq 4\sum_{cyc}x^7yz가 되므로 이것만 보이면 된다.

이를 위해 산술기하 평균 부등식으로 먼저 x^9+x^9+x^3y^3z^3 \geq 3x^7yz임을 보인다. 여기에서 \displaystyle 2\sum_{cyc}x^9+3x^2y^2z^2 \geq 3\sum_{cyc}x^7yz임을 보일 수 있다. 여기에 \sum_{cyc}x^9 \geq \sum_{cyc} x^7yz가 산술기하 평균 부등식 혹은 Muirhead 부등식으로 성립하므로 더해주면 원하는 결과가 증명이 된다.

등호는 x=y=z, 즉 a=b=c이므로 삼각형 ABC가 정삼각형일 때 성립한다.

2009 KMO 겨울학교 모의고사 2차 조합부등식

다음은 2009년 1월에 있었던 KMO 겨울학교의 모의고사 2차에 나온 문제이다.

n>=0인 정수에 대해, \sum_{i+j+k=n} \frac{(3i)!}{i!^3}\frac{(3j)!}{j!^3}\frac{(3k)!}{k!^3} \leq 27^n임을 보여라.

생긴게 참 조합적으로 의미도 있어 보이고, 실제로 작은 n 몇 개 대입하면 갭이 크기 때문에 조합적으로 쉽게 증명이 되리라 생각되어도 잘 안 된다.

풀이는 생성함수를 이용한다. \frac{1}{(1-27x)^{1/3}}\sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n을 비교하자. 좌변은 Newton 이항 정리를 이용한다. 그 식은 (1-27x)^{-1/3}이므로
\displaystyle \sum_{n \geq 0} \binom{-1/3}{n}(-27x)^n=\sum_{n \geq 0}\frac{(-\frac{1}{3})(-\frac{4}{3})\cdots(-\frac{3n-2}{3})}{n!}(-27)^nx^n
\displaystyle = \sum_{n\geq 0} \frac{1 \cdot 4 \cdot \cdots \cdot (3n-2)}{n!}9^n x^n
\displaystyle \geq \sum_{n\geq 0} \frac{(3n)!}{n!(3 \cdot 6 \cdot \cdots \cdot 3n)^2}9^nx^n
\displaystyle =\sum_{n\geq 0} \frac{(3n)!}{(n!)^3}x^n이 된다. 즉 \frac{1}{(1-27x)^{1/3}}x^n의 계수를 a_n, \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^nx^n의 계수를 b^n이라 하면 a_n \geq b_n이 성립한다.

따라서 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수는 \displaystyle \sum_{i+j+k=n}a_ia_ja_k이고 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수는 \displaystyle \sum_{i+j+k=n}b_ib_jb_k이므로 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수, 즉 주어진 식의 우변이 \displaystyle \sum_{i+j+k=n}a_ia_ja_k의 계수, 즉 주어진 식의 좌변보다 크거나 같다. 이로써 증명이 끝난다.

아직 조합적 풀이는 찾지 못했다.

이 부등식의 갭은 상당히 커서, 사실 \displaystyle \lim_{n \rightarrow \infty}\frac{(LHS)}{(RHS)}=0인 것도 증명이 가능하다. 이는 위의 풀이에서 조금만 더 연구하면 나오는 결과로, 원래 내가 이 문제를 모의고사에 낼 때엔 위의 문제만 냈는데 후배가 이를 개조해서 얻은 결과인 위의 리미트 문제를 part b로 추가해서 냈다. (중등부 모의고사엔 part a만이 나왔다.)

이 문제는 이미 알려진 다음 문제의 analogue이다.

n \geq 0인 정수에 대해, \displaystyle \sum_{i+j=n} \frac{(2i)!}{(i!)^2}\frac{(2j)!}{(j!)^2} = 4^n임을 보여라.

이 문제 역시 위에서 보인 방법과 똑같이 풀린다. 이 때엔 \frac{1}{\sqrt{1-4x}}의 계수를 구하면 그것이 \binom{2n}{n}이 됨을 보이면 된다.

이 등식의 경우 조합적인 풀이가 있다. (찾아내는 것은 다소 힘들긴 하지만, 풀이 자체는 간단하다.) 그 풀이는 다음과 같다. 먼저 (0,0)에서 북동쪽↗과 남동쪽↘으로 2n번 이동하는 경로들을 생각하자. 자유롭게 움직여도 된다. 그러면 매번마다 두 번의 선택이 있으므로 경우의 수는 총 2^{2n}=4^n이다. 한 편, 이 경로가 x축과 마지막으로 만나는 곳을 (2(n-k),0)이라 하자. (x좌표가 짝수임은, 움직일 때마다 y좌표의 기우성이 달라지는데 처음과 마지막이 둘 다 0이면 움직인 횟수가 짝수번이어야하기 때문이다.) 그러면 시작부터 (2(n-k),0)까지 움직이는 횟수는 45도 돌려서 생각하면 (0,0)에서 (n-k,n-k)까지 오른쪽과 위쪽으로 움직이는 경우의 수가 되어 \binom{2(n-k)}{n-k}이다. 그럼 이제 보여야할 사실은 하나다. (2(n-k),0)에서 (혹은 그냥 (0,0)에서) 2k번 움직이되 x축에 닿지 않는 경우의 수가 \binom{2k}{k}임을 보이면 된다.

이를 45도 돌려서 생각하면, (0,0)에서 2k번 움직이되 y=x와 닿지 않게 움직이는 경우의 수가 \binom{2k}{k}임을 보이는 것이 된다. 맨처음에 위로 올라갈 수도 있고 오른쪽으로 갈 수도 있으니 한 경우를 보아 2를 곱한다. 일반성을 잃지 않고 y=x 밑으로 움직이는 경우의 수를 생각하자. 그러면 이 상황을 x축 방향으로 -1만큼 움직이면 y=x 이하로 (이번엔 닿아도 된다) 2k-1번 움직이는 경우의 수가 된다. 그 마지막 점은 (k,k-1),(k+1,k-2),\cdots,(2k-1,0)이 되는데 그 중 하나 잡아 (k-1+i,k-i)로 가는 경우의 수를 세자.

방법은 카탈란 수열을 계산하는 조합적 방법와 동일하다. y=x를 넘는 경우 최초로 넘게 되는 곳을 (a,a+1)라 할 때 그 이후의 결과는 y=x+1에 대해 대칭해버리면 그 결과는 (0,0)에서 (k-i-1,k+i)로 가는 경로가 되며, 임의의 이런 경로는 반드시 y=x를 넘어야 하므로 또 최초로 넘는 순간에 대해 그 이후를 y=x+1에 대해 대칭시키면 원래 조건을 만족시키는 경로가 된다. 따라서 그 경우의 수는 \binom{2k-1}{k+i}가 된다. 곧 원래 조건을 만족시키는 경우의 수는 \binom{2k-1}{k-1+i} -\binom{2k-1}{k+i}이 된다.

따라서 y=x 밑으로 2k-1번 움직이는 총 경우의 수는 \displaystyle \sum_{i=1}^k \left( \binom{2k-1}{k-1+i} -\binom{2k-1}{k+i} \right) = \binom{2k-1}{k}가 된다. (마지막 항의 \binom{2k-1}{2k}는 0으로 친다. 실제로 위의 과정에서 생각해도 0이어야 하고.) 따라서 총 경우의 수는 2\binom{2k-1}{k}=2\binom{2k-1}{k-1}=\binom{2k}{k}이다. 이로써 이 조합등식이 증명된다!

물론 맨 처음의 문제를 만들게 된 계기는 이 문제였다. 매우 단순한 일반화.

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를 얻을 수 있기 때문이다.

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