Archive for the ‘ 자작 문제 소개 ’ Category

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

더블 카운팅하니 한 문제 더. 얼마 전에 있었던 여름학교 모의고사의 2차 2번. 2차 1번과 마찬가지로 이번에 출제한 문제.

48명의 학생이 7개의 문제가 주어지는 경시대회에 참가한다. 시험이 끝난 후, 다음과 같은 사실이 알려졌다.
– 임의의 5문제에 대해 그들을 전부 푼 학생은 없었다.
– 임의의 3문제에 대해 그들을 전부 푼 학생은 정확히 5명이었다.
– 임의의 1문제에 대해 그를 푼 학생 수는 짝수였다.
이 때 한 문제만 푼 학생은 정확히 한 명임을 보여라.

문제에서 더블 카운팅을 써달라고 애원하는 것이나 마찬가지. 첫 조건에 의해 학생이 푼 문제 수는 4개 이하다. 4,3,2,1,0개의 문제를 푼 학생 수를 a,b,c,d,e라 하자. 그러면 d=1을 보이면 된다.
{(문제 A,B,C, 학생 X): X가 A,B,C를 풂}을 생각한다.
(1) 두 번째 조건에 의해, 원소의 개수는 5\binom{7}{3}=175.
(2) 한 편, 이 원소의 개수는 \binom{4}{3}a+\binom{3}{3}b=4a+b이다.
따라서 이 두 조건에 의해 4a+b=175가 된다. 여기서 음 아닌 정수 k에 대해 a=43-k,b=3+4k라 할 수 있다. 한 편, a+b+c+d+e=48이므로 48=a+b+c+d+e \geq a+b=46+3k가 되어 k=0이 된다. 곧 a=43,b=3,c+d+e=2가 된다.
한 편, 이번엔 {(문제 A, 학생 X): X가 A를 풂}을 보면 세 번째 조건에 의해 그 원소의 개수 4a+3b+2c+d는 짝수가 되어 bd는 기우성이 같다. 즉 d는 홀수가 되는데 d \leq c+d+e=2이므로, d=1이고 문제가 증명된다.

나중에 들은 이야기지만 이 문제가 2차 시험 중에서 가장 평균이 높았다고. 이제 더블 카운팅도 많이 정립된건가..

Advertisements

2010 KMO 여름학교 모의고사 2차 #1

그동안 이것저것 일이 많아서 너무 오래 손을 놓고 있었다. 이번에 여름학교에 갔을 때가 마친 모의고사 보기 전이었기에 몇 문제를 propose했고 일부는 모의고사로 출제되었다. 다음은 그 중 한 문제.

예각 부등변 삼각형 ABC에 대해 A에서 BC에 내린 수선의 발을 P라 하고, BC,CA,AB의 중점을 각각 D,E,F라 하자. 그리고 P에서 DE,DF에 내린 수선의 발을 연결한 직선을 l_a라 하자. 마찬가지로 l_b,l_c를 정의하면 l_a,l_b,l_c는 한 점에서 만남을 보여라.

사실 이 문제 논증으로 풀려고 하면 의외로 어렵다. 나도 논증 풀이는 잘 모르겠다. 단지 확실한 것은 해석 기하 풀이가 길지 않게 반드시 존재하기 때문에 너무 어려운 포지션으로 나오기도 힘들다는 것이었다. 그래서 1번으로 냈는데, 별로 평균 점수는 그렇게 높지 않게 나타난 것 같다고.

당시 문제를 감수했던 L이 논증 풀이를 하나 제시하긴 했는데, 다소 복잡했던 것 같아 신경을 못 썼다. 매쓰링크에 올려보니 논증풀이가 올라오긴 왔는데 orthopole이란 개념을 쓰고 있더라. 현역 시절에도 사영기하 쪽은 하나도 안 들여다보았고 지금도 생소한 개념이라 읽기가 꺼려진다. 그래도 언젠가 한 번 봐야지..

논증 풀이 환영.

1986 IMO Short-list 기하 문제와 관련 부등식

원래 1986년 쇼트리스트 문제 중에 다음과 같은 문제가 있었다.

삼각형 ABC의 외심을 O, 내심을 I, 내접원과 세 변의 접점을 D,E,F, 삼각형 DEF의 구점원의 중심을 X라 하자. O,I,X가 일직선 위에 있음을 증명하여라.

이 문제에서 조금 더 나아가 길이를 비교하여 다음 기하 부등식을 얻어낼 수 있다. (정확히는 그 길이의 비를 구할 수 있다.) 대략 2006년 쯤에 발견한 결과로 기억한다.

OI \geq 4IX임을 보여라.

앞의 문제를 (a), 뒤의 문제를 (b)라 한다.

First Solution. (a) 삼각형 DEF에서 외심이 I이고 구점원의 중심이 X이므로, 무게중심을 G라 하면 IX=\frac{3}{2}IG이며 I,X,G는 일직선 위에 있다. 이제 O,I,G가 일직선 위에 오며 OI \geq 6IG임을 보이자.
\vec{OA}=\vec{a}이라 하고 나머지도 마찬가지로 정의한다. \vec{OI}=\sum \frac{a}{a+b+c}\vec{a}이며 \vec{OG}=\frac{1}{3}(\vec{OD}+\vec{OE}+\vec{OF})=\frac{1}{3}\sum \frac{s-c}{a}\vec{b}+\frac{s-b}{a}\vec{c}=\sum \frac{1}{3}(\frac{s-b}{c}+\frac{s-c}{b})\vec{a}이고 \vec{0}=\sum \sin{2A} \vec{a}이므로 O,I,G가 일직선 위에 있음을 보이기 위해 \vec{OG}\vec{OI}의 스칼라 배수임을 보이면 되고, 그를 위해 \vec{OG}+k\vec{0}=l\vec{OI}가 되는 상수 k,l이 존재함을 보이면 된다. 여기서 la,b,c에 대한 대칭식이 될 것이므로, \vec{OG}+k\vec{0}\vec{OI}\vec{a}의 계수의 비율이 l, 즉 대칭식이 되게 하는 대칭식 k를 잡으면 된다. 그 비율은 \displaystyle \frac{\frac{1}{3}(\frac{s-b}{c}+\frac{s-c}{b})+k\sin{2A}}{\frac{a}{a+b+c}}이므로 이를 계산하자.

\displaystyle \frac{\frac{1}{3}(\frac{s-b}{c}+\frac{s-c}{b})+k\sin{2A}}{\frac{a}{a+b+c}}
\displaystyle = \frac{a+b+c}{3}\frac{\frac{s-b}{c}+\frac{s-c}{b}+3k\sin{2A}}{a}
\displaystyle = \frac{a+b+c}{3abc}(b(s-b)+c(s-c)+3kbc\sin{2A})이므로, \vec{b}의 계수는 \displaystyle \frac{a+b+c}{3abc}(a(s-a)+c(s-c)+2kac\sin{2B})이므로 두 값이 로 같음은 곧 \displaystyle b(x-b)+c(s-c)+3kbc\sin{2A}=a(s-a)+c(s-c)+3kac\sin{2B}임과 동치이다. 여기에서 3kc(b\sin{2A}-a\sin{2B})=a(s-a)-b(s-b)=(a-b)s-(a-b)(a+b)=-(a-b)(s-c)가 되어
\displaystyle k=\frac{-(a-b)(s-c)}{3c(b\sin{2A}-a\sin{2B})}=\frac{-(a-b)(s-c)}{6bc\frac{a}{2R}\frac{-a^2+b^2+c^2}{2bc}-6ac\frac{b}{2R}\frac{a^2-b^2+c^2}{2ac}}
\displaystyle =\frac{2R}{3}\frac{-(a-b)(s-c)}{-(a-b)(a+b)^2+(a-b)c^2} = \frac{2R}{3}\frac{s-c}{(a+b+c)(a+b-c)}=\frac{R}{3(a+b+c)}가 된다. 따라서 대칭식이 되어 증명이 끝난다.

(b) 앞의 결과에서 k=\frac{R}{3(a+b+c)}를 대입하자. 그러면
\displaystyle l=\frac{a+b+c}{3abc}(b(s-b)+c(s-c)+\frac{R}{a+b+c}2bc \sin{A} \cos{A}) = \frac{a+b+c}{3abc}(b(s-b)+c(s-c)+\frac{R}{a+b+c}\frac{a}{2R}(-a^2+b^2+c^2))
\displaystyle = \frac{1}{6abc}(-\sum_{cyc}a^3+\sum_{sym}a^2b+4abc)=\frac{1}{6abc}((-a+b+c)(a-b+c)(a+b-c)+6abc)
이다. 곧 \displaystyle \frac{OG}{OI}=\frac{(-a+b+c)(a-b+c)(a+b-c)}{6abc}+1이므로 \displaystyle \frac{IG}{OI}=\frac{(-a+b+c)(a-b+c)(a+b-c)}{6abc}가 된다. IX=\frac{3}{2}IG임에서 \displaystyle \frac{IX}{OI}=\frac{1}{4}\frac{(-a+b+c)(a-b+c)(a+b-c)}{abc} \leq \frac{1}{4}가 되어 OI \geq 4IX가 성립한다.

Second Solution. (a) 내접원과 BC,CA,AB의 접점을 D,E,F라 하자. 그리고 EF,FD,DE의 중점을 각각 P,Q,R이라 하자. 그러면 XPQR의 외심이다. 삼각형 AEF는 이등변 삼각형이므로 A,P,I는 한 직선 위에 있게 된다. (I는 내심으로 각 A의 이등분선 위에 있음) 이 때 \angle{APF}=\angle{AFI}=\frac{\pi}{2}이고 \angle{PAF}=\angle{FAI}이므로 삼각형 PAF와 삼각형 FAI는 닮음이다. 따라서 IP:IF=IF:IA, 즉 IA \cdot IP=IF^2이다. 이 때 내접원의 반지름의 길이를 r이라 하면 IA \cdot IP=r^2이다. 마찬가지로 IB \cdot IQ = IC \cdot IR = r^2임을 얻을 수 있으므로, 이 평면을 ABC의 내접원에 대해 반전하면 A \rightarrow P,B\rightarrow Q,C \rightarrow R이 되므로 ABC의 외접원은 PQR의 외접원으로 반전된다.

한 편, 이 외접원을 반전할 때 원래의 중심을 O라 하면, 반전된 후의 도형인 원의 중심은 X가 된다. 원래의 원은 직선 OI에 대해 대칭이므로 그 반전 역시 직선 OI의 반전, 즉 직선 OI에 대해 대칭이어야 한다. 따라서 X가 직선 OI 위에 있어야 하고 이는 O,I,X가 일직선 위에 있음을 증명하는 것이 된다. 이로써 증명은 끝난다.

(b) 직선 OI 위에서 생각하자. 이 수직선 위에서 I의 좌표를 0이라 하면 O의 좌표는 OI=\sqrt{R^2-2Rr}가 된다. 곧 외접원의 지름 양 끝점은 \sqrt{R^2-2Rr} \pm R이 되어 원 X의 지름 양 끝점은 \frac{r^2}{\sqrt{R^2-2Rr} \pm R}가 된다. 따라서 X의 좌표는 \displaystyle \frac{1}{2}(\frac{r^2}{\sqrt{R^2-2Rr}+R}+\frac{r^2}{\sqrt{R^2-2Rr}-R})=-\frac{r}{2R}\sqrt{R^2-2Rr}이 되므로 \frac{IX}{OI}=\frac{r}{2R} \leq \frac{1}{4}가 되어 증명된다.

Third Solution. OI^2 \geq 16IX^2를 보인다. 삼각형 DEF의 수심을 H이라 하면 구점원의 중심은 IH의 중점이다. IH^2=9r^2-(DE^2+EF^2+FD^2)이므로 IX^2=\frac{1}{4}(9r^2-\sum DE^2)이다. DE=2r \cos \frac{C}{2}이므로
\displaystyle 16IX^2 = 4(9r^2-4r^2(\sum \cos^2\frac{A}{2}))=4(9r^2-4r^2 \sum \frac{1+\cos A}{2})
\displaystyle = 12r^2-8r^2 \sum cos A인데, \sum \cos A = 1+\frac{r}{R}이므로 16IX^2=12r^2-8r^2(1+\frac{r}{R})가 된다. 따라서
\displaystyle R^2-2Rr=OI^2 \geq 16IX^2
\displaystyle \Leftrightarrow R^2-2Rr \geq 12r^2 -8r^2(1+\frac{r}{R})
\displaystyle \Leftrightarrow R^3-2R^2r-4Rr^2+8r^3 \geq 0
\displaystyle \Leftrightarrow (R-2r)^2(R+2r) \geq 0
인데 이 부등식은 성립하므로, 원래 부등식이 성립한다.

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

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