Archive for August, 2010

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 JMO #3

3. 2010개의 섬이 있고, 그 섬들을 연결하는 2009개의 다리가 있다. 어떤 두 개의 섬에 대해서도 1개의 다리가 둘을 연결하거나 다리가 없거나 둘 중의 하나라 하고, 다리의 양 끝은 서로 다른 두 개의 섬이라 하자. 또한, 임의의 두 섬을 골라도 한 섬에서 다른 섬으로 다리를 몇 번 건넘으로써 갈 수 있다고 한다.
이제, 모든 섬이 한 통의 편지를 임의의 섬에 보낸다고 한다. (단, 자기 자신에게 편지를 보내는 것도 가능하다.) 이 때, 다음 사실이 판명되었다.
“섬 A와 섬 B가 다리로 연결되어 있으면, 섬 A의 편지의 목적지와 섬 B의 편지의 목적지는 서로 다리로 연결된 두 섬이거나, 같은 섬이다.
이 때, 다음 (1)과 (2) 중 적어도 하나가 성립함을 보여라.
(1) 자기 자신에게 편지를 보낸 섬이 존재한다.
(2) 서로 편지를 교환하고, 다리로 연결되어 있는 두 섬이 존재한다.

그래프로 바꾸면 단순그래프인데 2010개의 점, 2009개의 변을 갖고 있고 연결그래프가 되어야 한다. 곧 이 그래프는 수형도로 회로가 없다. 편의상 도시 X가 편지를 보낸 도시를 f(X)라 하자. 그러면 보여야할 것은 f(X)=XX가 존재함을 보이거나 f(X)=Y,f(Y)=XX,Y가 존재함을 보이면 된다. 귀류법으로 그런 경우가 없음을 가정하자. 그리고 수형도이기 때문에 X에서 f(X)로 가는 경로는 유일하게 존재하는데 그 길이를 d(X)라고 하자.

먼저 임의의 도시 X_0을 택한다. 그리고 d(X_0) \geq 2임을 가정하자. 그러면 X_0에서 f(X_0)으로 가는 경로가 있는데 그 경로에서 X_0 바로 다음 점을 X_1이라 한다. 마찬가지로 X_1에서 f(X_1)으로 가는 경로에서 X_1의 다음 점을 X_2라 하고, 계속 정의한다. 그러면 0 \leq d(X_{i+1})-d(X_i) \leq 2임을 보일 수 있다. 그런데 d(X_{i+1})=d(X_i)인 경우는 X_i에서 f(X_i)까지 이어진 경로 위에 f(X_{i+1})이 없음을 의미한다. 즉 새로운 점이 하나 필요하게 된다. 따라서 d(X_{i+1})=d(X_i)인 경우는 무수히 많이 나올 수 없어서 d(X_i)는 계속 감소해야만 한다. 그러면서도 0이 되어선 안 된다. (d(X_i)=0이면 X_i=f(X_i), 모순) 그러면 언젠가 d(X_n)=1n이 존재하게 된다. (만약 d(X_0)=1이었다면 바로 n=0인 경우로 보면 된다.)

이제 m \geq n인 경우 X_{m+1}=f(X_m)이 되어야 한다. 이 때 앞에서와 비슷한 논의로 계속 새로운 점이 나올 수 없어서 언젠가 f(X_m)=X_m이거나 f(X_m)=X_{m-1}이 되어야 한다. 이는 모순. 끝

풀기 전에 좀 브레인스토밍하다보면 문제가 어떤 의미인지 또 어떤 풀이인지 감은 잡히는데 그걸 표현하는게 다소 짜증나는 문제

2010 JMO #2

2. k를 양의 정수, m을 홀수로 놓는다. 이 때, n^n - m2^k의 배수가 되게 하는 n이 존재함을 보여라.

수학적 귀납법. base case는 자명하고.. 1^1,3^3,\cdots,(2^k-1)^{2^k-1}가 mod 2^k1,3,\cdots,2^k-1이 됨을 가정하자. 임의의 홀수 1 \leq m \leq 2^k-1에 대해 (2^k+m)^{2^k+m} \equiv m^{2^k+m} \equiv m^m\text{ (mod }2^k\text{)}가 된다. (페르마의 정리나 오일러의 정리에 의해 임의의 홀수 x에 대해 x^{2^{k-1}} \equiv 1\text{ (mod }2^k\text{)}가 됨을 확인할 수 있다.) 한 편 (2^k+m)^{2^k+m} = m^{2^k+m} + \binom{2^k+m}{1} m^{2^k+m-1} 2^k + \binom{2^k+m}{2} m^{2^k+m-2} 2^{2k} + \cdots
\equiv m^{2^k+m} + (2^k+m)m^{2^k+m-1} 2^k \equiv m^m + 2^k\text{ (mod }2^{k+1}\text{)}가 되므로 mod 2^k에서 mod 2^{k+1}로 옮겨지는 과정에서 역시 모든 홀수가 나온다. 끝

귀납법 안쓰는 풀이 없을까나.. 한 방에 풀리는 풀이

2010 JMO #1

1. AB \neq AC인 예각삼각형 ABC가 있어 A에서 BC에 내린 수선의 발을 H라 하자. 점 P,Q를 세 점 A,B,P와 세 점 A,C,Q가 동시에 이 순서대로 일직선 상이 오게 했더니 네 점 B,C,P,Q가 한 원 위에 있으며 HP=HQ가 성립한다고 한다. 이 때 H는 삼각형 APQ의 외심임을 보여라. 단, XY로 선분 XY의 길이를 표시한다고 한다.

P,Q는 반직선 AB,AC 위에 있도록 한다. B,C,P,Q가 일직선이 되도록 하는 PQ들은 전부 서로 평행하다. 그들에 대해서 PQ의 수직이등분선도 바뀐다. (AB \neq AC이기 때문에) 즉 HP=HQ이며 B,C,P,Q가 한 원 위에 있단 조건을 만족시키는 PQ는 하나. 마찬가지로 HAPQ의 외심이 되는 PQ도 하나 뿐이다. (AH=HP인 것 자체가 A=P 제외하면 하나 뿐이니) 따라서 동일법을 써서 HAPQ의 외심이 되는 경우 B,C,P,Q가 한 원 위에 있음을 보이면 된다. 그런데 이런 경우 AH=HP이고 \angle BAH = \frac{\pi}{2}-B니까 정리하면 AP=2h \sin B가 된다. (h=HA) 마찬가지로 AQ=2h \sin C가 되어 AP \cdot AB = 2hc \sin B = \frac{hbc}{R} = 2hb \sin C = AQ \cdot AC가 된다. (R은 외접원 반지름 길이) 끝

뭐 그냥저냥..

2010 KMO 여름학교 “조합등식” 강의록

저번 8월의 여름학교에 조합론 강의를 했다. 많은 토픽 중에서 조합 등식에 대해 강의를 하였는데 그 때 나누어주었던 강의록을 올린다. 사실 중등부의 프린트는 아주 약간 다른 버젼이긴 한데, 차이래봤자 중등부엔 이항계수에 대한 개념적 설명이 더 추가됐고 맨 마지막 J 챕터를 없앤 것에 불과하니 고등부 버젼을 올린다. 조합등식이 올림피아드에 반드시 나오리란 보장도 없지만 증명하면서 많은 테크닉을 익힐 수 있어 더 없이 좋은 연습문제가 되리라 생각. 게다가 2010 USA TST #8로 조합등식 문제가 하나 나오기도 했지..

챕터 미리보기!

A. 조합등식이란
B. 생성함수
C. 생성함수의 이용 리뷰
D. 기초 조합등식
E. 포함과 배제의 원리
F. 차분법
G. 부호가 붙은 조합등식
H. 응용 조합등식
I. 심화 조합등식
J. 도전 조합등식

파일: 조합등식 강의록

2010 Iran NMO #1

2010 Iran NMO 풀이 마지막.

1. a,b는 두 양의 정수로 a > b이다. \gcd(a-b,ab+1)=1임과 \gcd(a+b,ab-1)=1이 알려져 있을 때. (a-b)^2+(ab+1)^2는 완전제곱수가 아님을 보여라.

(a-b)^2+(ab+1)^2=(a+b)^2+(ab-1)^2=(a^2+1)(b^2+1)임을 이용한다. 만약 완전제곱수라 가정하자. 이 때 소수 pa^2+1,b^2+1을 나눈다고 가정하자. 즉 a^2 \equiv b^2 \equiv -1\text{ (mod }p\text{)}가 된다. 따라서 a \equiv \pm b가 된다. 만약 a-b \equiv 0이라면 맨 위의 식에서 p^2(a-b)^2+(ab+1)^2를 나눔에서 pab+1도 나누는데 이는 a-b,ab+1이 서로 소임에 모순. 마찬가지로 a+b \equiv 0ab-1p의 배수가 되어 서로 소란 가정에 모순이 된다. 따라서 a^2+1,b^2+1은 서로 소인데 곱이 완전제곱수이므로 각각이 제곱수가 된다. 그런데 a^2+1이 제곱수인 양의 정수 a는 없으니까 모순. 끝

전반적으로 문제들이 쉬운 감이 없지 않았다. 적어도 KMO가 더 어려워보인다. ㅠ

2010 Iran NMO #4

4. P(x)=ax^3+bx^2+cx+d는 실계수 다항식으로 \min\{d,b+d\} > max\{|{c}|,|{a+c}|\}이라 한다. P(x)는 구간 [-1,1]에서 실근을 갖지 않음을 보여라.

p(x) 말고 q(x)=dx^3+cx^2+bx+a를 보도록 한다. 주어진 조건은 d,b+d > c,-c,a+c,-a-c이므로 이들을 이용한다. 참고로 d는 절대값보다 크므로 양의 실수이다. q'(x)=3dx^2+2cx+b가 2차함수인데 그 축의 x 좌표는 1 \geq -\frac{c}{3d} \geq -1 \Leftrightarrow -3d \leq c \leq 3d3d \geq d \geq cc \geq -d \geq -3d로 성립한다. 따라서 x \leq -1일 땐 q'는 감소함수인데 q'(-1)=3d-2c+b=(b-c+d)+(-c+d)+d > 0이므로 q'(x) > 0이다. 또한 x \geq 1일 때 q'가 증가함수가 되어 q'(1)=3d+2c+b=(b+c+d)+(c+d)+d > 0임에서 역시 q'(x) >0 0이다. 곧 q(x)x \leq -1, x \geq 1일 때 증가한다. x \leq -1일 땐 q(x) \leq q(-1)=-d+c-b+a < 0이 되고 x \geq 1일 땐 q(x) \geq q(1)=d+c+b+a > 0이 된다. 따라서 qx \leq -1, x \geq 1일 땐 해를 갖지 않는다. x^3 q(\frac{1}{x})=p(x)이므로 이는 -1 \leq x \leq 1이며 x \neq 0일 때 p가 해를 갖지 않음을 의미한다. 마지막으로 p(0)=d > 0이므로 결국 p[-1,1]에서 해를 갖지 않는다.