Posts Tagged ‘ 2009 ’

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}이다. 이로써 이 조합등식이 증명된다!

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

Advertisements

2009 IMO Short-list

작년 독일 IMO의 후보 문제.

ALGEBRA

A1. 다음 조건을 만족하는 최대의 정수 k를 구하여라: 2009개의 삼각형이 주어져 있다. 임의의 삼각형에 대해 세 변을 파랑, 빨강, 하양이 하나씩 나오도록 칠한다. 이제 각각의 색깔에 대해 변의 길이들을 정렬하여 파란 변의 길이를 b_1 \leq b_2 \leq \cdots \leq b_{2009}, 빨간 변의 길이를 r_1 \leq r_2 \leq \cdots \leq c_{2009}, 하얀 변의 길이를 w_1 \leq w_2 \leq \cdots \leq w_{2009}라 하자. 이 때 k개의 j가 있어 변의 길이가 b_j,r_j,w_j인 삼각형이 존재한다.

A2. 세 양의 실수 a,b,c\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=a+b+c를 만족할 때 다음 부등식이 성립함을 보여라.
\displaystyle \sum_{cyc} \frac{1}{(2a+b+c)^2} \leq \frac{3}{16}

A3. 양의 정수의 집합에서 양의 정수의 집합으로 대응되는 함수 f가 임의의 x,y에 대해 x,f(y),f(y+f(x)-1)이 삼각형의 세 변의 길이가 되도록 한다. 이런 f를 모두 구하여라.

A4. ab+bc+ca \leq 3abc를 만족하는 양의 실수 a,b,c에 대해 다음 부등식이 성립함을 보여라.
\displaystyle \sum_{cyc} \sqrt{\frac{a^2+b^2}{a+b}} +3 \leq \sqrt{2}(\sum_{cyc}\sqrt{a+b})

A5. 실수의 집합에서 실수의 집합으로 대응되는 임의의 함수 f가 주어져 있다. 이 때 f(x-f(y))> yf(x)+x가 성립하는 실수 x,y가 존재함을 보여라.

A6. 강증가하는 수열 s_1,s_2,s_3,\cdots의 부분수열 s_{s_1},s_{s_2},\cdotss_{s_1+1},s_{s_2+1},\cdots가 등차수열이라 한다. 이 때 s_1,s_2,\cdots가 등차수열임을 보여라.

A7. 임의의 실수 x,y에 대해 다음 식이 성립하는 함수 f:\mathbb{R} \rightarrow \mathbb{R}을 모두 구하여라.
\displaystyle f(xf(x+y))=f(yf(x))+x^2

COMBINATORICS

C1. 2009장의 카드가 있는데, 이 카드는 한 면은 금색이고 한 면은 검은 색이다. 이들을 일렬로, 금색 면이 앞면으로 나오도록 늘어놓는다. 두 명의 사람은 다음과 같은 시행을 번갈아가며 한다. 각 사람은 맨 왼쪽 카드가 금색 카드가 되도록 연속한 50장의 카드를 선택한 후, 이 카드들을 각각 뒤집는다. 더 이상 시행이 불가능한 시점까지 이들이 시행을 했을 때 마지막으로 시행을 한 사람이 이긴다고 한다.
(a) 이 게임은 유한 시간 내에 끝나는가?
(b) 첫 번째 사람에게 필승수가 존재하는가?

C2. 임의의 정수 n \geq 2에 대해, N(n)을 다음 조건을 만족시키는 음 아닌 정수 (a_i,b_i,c_i), i=1,\cdots,N(n)이 성립하게 하는 수의 최댓값이라 하자.
(1) 임의의 i에 대해 a_i+b_i+c_i=n
(2) i \neq j이면 a_i \neq a_j, b_i \neq b_j, c_i \neq c_j
n \geq 2에 대해 N(n)을 구하여라.

C3. e_1,...,e_{n-1}을 0,1 중에서 아무렇게나 택한다. 그리고 a_0=1, a_1=7이라 하고 (1) e_i=0이면 a_{i+1}=2a_{i-1}+3a_i, (2) e_i=1이면 a_{i+1}=3a_{i-1}+a_i가 되도록 정의하고 b_0=1, b_1=7, (1) e_{n-i}=0이면 b_{i+1}=2b_{i-1}+3b_i, (2) e_{n-i}=1이면 b_{i+1}=3b_{i-1}+b_i로 정의한다. 이 때 a_n=b_n이 성립함을 보여라.
(C3는 여기에서 풀이를 다루었다.)

C4. m \geq 1인 정수에 대해, 2^m \times 2^m 모양의 체스판을 체스판의 칸들로 이루어진 직사각형들로 분할하려 한다. 이 때, 왼쪽 밑에서 오른쪽 위로 내려가는 큰 대각선 위에 놓이는 2^m개의 칸들은 각각 길이가 1인 정사각형으로 미리 분할해놓는다. 이 때 이러한 분할들의 직사각형들의 둘레의 길이의 합의 최솟값을 구하여라.

C5. 다섯 개의 비어 있는 2리터짜리 물통이 정오각형의 각 꼭지점 위에 놓여 있다. 신데렐라와 그녀의 나쁜 계모가 다음과 같은 시행을 한다. 각 턴마다, 계모는 1리터의 물을 가까운 강에서 떠와서 다섯 개의 물통들에 임의로 나누어준다. 그러면 신데렐라는 인접한 두 개의 물통을 잘 골라서 그 물통의 물들을 강물에 버리고 다시 제자리에 되돌려 놓는다. 그리고 다음 턴이 시작된다. 계모의 목표는 물통들 중 하나라도 넘치게 만드는 것이다. 신데렐라의 목표는 그것을 막는 것이다. 나쁜 계모는 목표를 달성할 수 있을까?

C6. 999 \times 999 모양의 칸에 림프룩이란 말이 다음과 같이 움직인다. 어느 칸에 있더라도 이 말은 그에 인접한 모든 칸으로 움직일 수 있다. 단, 한 번 움직일 때마다 방향을 틀어야 한다. 즉, 연속한 두 번의 움직임은 반드시 수직이어야 한다. 림프룩의 좋은 길이란 칸들로 이루어진 수열인데 모든 칸들이 서로 다르고, 림프룩이 그 순서로 위의 조건에 맞게 움직일 수 있어야 하는 것을 뜻한다. 만약 림프룩이 좋은 길로 다 지나온 후에 한 번 더 움직여서 처음 위치로 돌아올 수 있으면 이 좋은 길을 굉장한 길이라 하자. 굉장한 길 중에서 가장 긴 길은 몇 칸을 차지하는가?

C7. 임의의 정수 n \geq 2에 대해, n의 십진법 전개에 다음 시행을 거쳐 정수 h(n)을 만든다. rn의 가장 오른쪽 끝의 자리수라 하자.
(1) 만약 r=0이면, h(n)n의 십진법 전개에서 맨 오른쪽의 0을 지워서 얻는다.
(2) 만약 1 \leq r \leq 9이면, r 이상의 자리수로 이루어진 n의 오른쪽 끝 부분 중 가장 긴 부분을 R이라 하고, 그것을 제외한 왼쪽 부분을 L이라 하자. (L은 아무 글자도 없는 공집합일 수도 있다.) 그러면 h(n)은 먼저 L을 맨 앞에 쓴 후 R-1을 두 번 써서 얻는다. 예를 들면, n=17151345543일 때 L=17151, R=345543, h(n)=17151345542345542가 된다.
임의의 정수 n \geq 2에서 시작하더라도, h를 유한번 적용시켜 마지막에 1을 만들 수 있음을 보여라.

GEOMETRY

G1. 삼각형 ABCAB=AC를 만족한다. 각 A,B의 이등분선이 변 BC,ACD,E에서 만난다. 삼각형 ADC의 내심을 K라 하고 \angle{BEK}=\frac{\pi}{4}라 한다. \angle{BAC}의 값을 구하여라.

G2. 삼각형 ABC의 외심을 O라 하자. 변 CA,AB 위에 각각 P,Q를 잡는다. 변 BP,CQ,PQ의 중점을 지나는 원 k를 잡자. 만약 직선 PQ와 원 k가 접하면 OP=OQ임을 보여라.

G3. 삼각형 ABC가 있다. 내접원이 변 AB,AC와 각각 Z,Y에서 접한다. BY,CZ의 교점을 G라 하고, 사각형 BCYRBCSZ가 평행사변형이 되도록 R,S를 잡는다. GR=GS임을 보여라.

G4. 원에 내접하는 사각형 ABCD의 대각선 AC,BDE에서 만나고 직선 AD,BCF에서 만난다. AB,CD의 중점을 각각 G,H라 하자. E,G,H를 지나는 원이 직선 EF와 점 E에서 접함을 보여라.

G5. 볼록이며 어떤 점 O에 대해 대칭인 다각형 P가 있다. 이 때 P \subset R인 평행사변형 R이 있어 \displaystyle \frac{|R|}{|P|} \leq \sqrt{2}이 되도록 할 수 있음을 보여라. 여기서 |R|,|P|는 각각 R,P의 넓이이다.

G6. 사각형 ABCD의 변 AB,CD는 평행이 아니고, AD,BC가 점 P에서 만난다. 삼각형 ABP,DCP의 외심을 각각 O_1,O_2, 수심을 각각 H_1,H_2라 하자. O_1H_1,O_2H_2의 중점을 각각 E_1,E_2라 하자. 이 때 E_1에서 CD에 내린 수선과 E_2에서 AB에 내린 수선과 H_1H_2는 한 점에서 만남을 보여라.

G7. 삼각형 ABC의 내심을 I라 하고 BIC,CIA,AIB의 내심을 각각 X,Y,Z라 하자. 삼각형 XYZ가 정삼각형이면 삼각형 ABC도 정삼각형임을 보여라.

G8. 원에 외접하는 사각형 ABCD에서 A를 지나는 직선 g가 변 BCM에서 만나고 직선 CDN에서 만난다. \triangle{ABM},\triangle{MNC},\triangle{NDA}의 내심을 각각 I_1,I_2,I_3이라 하자. 삼각형 I_1I_2I_3의 수심이 g 위에 옴을 보여라.

NUMBER THEORY

N1. 사교회에 n명이 있다. 이들은 번호 1,2,\cdots,n이 주어져 있다. 회원들은 다른 회원들에게 선물을 보내는데, 이 선물에는 그 회원이 이미 다른 회원에게서 받은 것도 포함된다. 어떤 회원이 보낸 선물을 다시 받게 되는 당혹스러운 불상사를 막기 위해, 사교회에서는 연차회의에서 다음과 같은 규칙을 발표했다.
a라는 번호를 가진 회원은 a(b-1)n의 배수여야만 b에게 선물을 보낼 수 있다.”
만약 모든 회원이 이 규칙을 따른다면, 위에서 설명한 불상사가 일어나지 않음을 보여라.

N2. 만약 N=1이거나 N이 서로 다를 필요는 없는 짝수 개의 소수의 곱으로 표현된다면 N을 균형잡힌 수라 하자. 주어진 양의 정수 a,b에 대해 다항식 PP(x)=(x+a)(x+b)로 정의하자.
(a) P(1),P(2),\cdots,P(50)이 전부 균형잡힌 수가 되는 서로 다른 양의 정수 a,b가 존재함을 보여라.
(b) 만약 모든 양의 정수 n에 대해 P(n)이 균형잡힌 수가 된다면 a=b임을 보여라.

N3. 상수함수가 아닌 함수 f:\mathbb{N} \rightarrow \mathbb{N}가 있어 임의의 서로 다른 a,b에 대해 a-bf(a)-f(B)을 나눈다고 한다. 이 때 무수히 많은 소수 p가 존재하여 어떤 c에 대해 pf(c)를 나눔을 보여라.

N4. 임의의 2 \leq k \leq n-1k에 대해 a_{k+1}=\frac{a_k^2+1}{a_{k-1}+1}-1을 만족시키는 양의 정수 수열 a_1,a_2,\cdots,a_n이 존재하는 양의 정수 n을 모두 구하여라.

N5. P(x)는 정수계수 다항식으로 상수함수가 아니다. 이 때 임의의 n \geq 1에 대해 T^n(x)=x를 만족하는 정수 x의 개수가 P(n)이 되는 함수 T:\mathbb{Z} \rightarrow \mathbb{Z}가 존재하지 않음을 보여라. 단 T^n이란 Tn번 합성한 함수이다.

N6. k는 양의 정수이다. 만약 임의의 n \geq 1에 대해 a_n=\frac{a_{n-1}+n^k}{n}가 성립하는 정수 수열 a_0,a_1,\cdots가 성립하면 k-2가 3의 배수임을 보여라.

N7. a,b는 1보다 큰 서로 다른 정수이다. 이 때 (a^n-1)(b^n-1)이 완전제곱수가 아닌 양의 정수 n이 존재함을 보여라.

2009 IMO Short-list C3

이번 IMO 쇼트리스트 문제 중에서 가장 흥미로웠던 문제.

e_1,...,e_{n-1}을 0,1 중에서 아무렇게나 택한다. 그리고 a_0=1, a_1=7이라 하고 (1) e_i=0이면 a_{i+1}=2a_{i-1}+3a_i, (2) e_i=1이면 a_{i+1}=3a_{i-1}+a_i가 되도록 정의하고 b_0=1, b_1=7, (1) e_{n-i}=0이면 b_{i+1}=2b_{i-1}+3b_i, (2) e_{n-i}=1이면 b_{i+1}=3b_{i-1}+b_i로 정의한다. 이 때 a_n=b_n이 성립함을 보여라.

즉 초기값은 1,7로 고정되어 있는데, 이진 수열이 주어져 있고 그것에 따라 점화식을 바꾸면 이진 수열을 거꾸로 주더라도 결과가 같게 나온다는 것이다. 밑의 풀이를 보면 알겠지만 일반적인 경우 다 되는 것은 아니고, 1과 7, 2와 3, 3과 1이 적당히 잘 주어져서 나온 결과이다. 러시아에서 제출한 문제.

이하는 official solution.

w=\sigma_1 \cdots \sigma_n이란 이진수열이 주어져 있을 때 이것을 거꾸로 한 것을 \bar{w}=\sigma_n \cdots \sigma_1이라 한다. 또한 \emptyset을 아무 글자도 없는 이진수열이라 하자. 이제 a_n=(u,v)^w,b_n=(u,v)^{\bar{w}}꼴이 되도록 다음과 같이 (u,v)^w를 잘 정의한다.

(u,v)^{\emptyset}=v, (u,v)^0=2u+3v,(u,v)^1=3u+v
(u,v)^{w\sigma \epsilon}=2(u,v)^w+3(u,v)^{w\sigma} (\sigma는 0 또는 1이며 \epsilon=0)
(u,v)^{w\sigma \epsilon}=3(u,v)^w+(u,v)^{w\sigma} (\sigma는 0 또는 1이며 \epsilon=1)
(정의에 매달리지 말고, 이것이 수열의 정의와 어떤 연관성이 있고 왜 이렇게 정의했는지의 필연성을 느껴보길 바란다.)

이 때 다음과 같이 multilinearity가 성립함을 확인할 수 있다.
(\lambda_1u_1+\lambda_2u_2,\lambda_1v_1+\lambda_2v_2)^w=\lambda_1(u_1,v_1)^w+\lambda_2(u_2,v_2)^w

이제 원래 문제로 돌아간다. 그러면 w=\epsilon_1 \cdots \epsilon_{n-1}이라 하면 a_n=(1,7)^w, b_n=(1,7)^{\bar{w}}가 성립한다. 이제 w의 길이에 대한 수학적 귀납법을 적용한다. 길이가 0이나 1인 경우는 자명하고 n \geq 2라 가정하자. 여기서 주로 쓰이게 되는 사실은 바로 \sigma가 0이든 1이든 (2,1)^{\sigma}=7이 성립한다는 것이다. 따라서 \epsilon=0인 경우 (1,7)^{w\sigma 0}=2(1,7)^w+3(1,7)^{w\sigma}=2(1,7)^{\bar{w}}+3(1,7)^{\sigma \bar{w}}=2(2,1)^{\sigma \bar{w}}+3(1,7)^{\sigma \bar{w}}=(7,23)^{\sigma \bar{w}}=(1,7)^{0\sigma \bar{w}}가 성립한다. 마찬가지로 \epsilon=1인 경우도 해결할 수 있다.

사실 (u,v)^w라는 꼴을 써야할 필요는 없이, 수학적 귀납법을 이용하여 길게 표현할 수 있다. 그러나 저 표현법이 실제로 매우 효율적이고 직관적이다. 결론적으로 풀다보면 결국 푸는 본질적 방향은 다들 비슷함을 알 수 있다. 흥미로운 문제.

(사실 왜 C인진 잘 모르겠다 ㅠ A로 놔도 할 말 없고 N으로 놓으면 조금 의아해도 원래 N에 수열 많으니까 할 말 없지만 C는 흠.. 점화식이라서?)