Posts Tagged ‘ Iran ’

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]에서 해를 갖지 않는다.

2010 Iran NMO #5

5. 삼각형 ABC에서 \angle{A}=\frac{\pi}{3}라 한다. AB,AC의 연장선 위에 E,F를 잡아 BE=CF=BC가 되도록 한다. 직선 EF가 삼각형 ACE의 외접원과 K에서 만난다고 하자. (단, K\neq E) 이 때 K\angle{A}의 이등분선 위에 있음을 보여라.

흠.. 이것도 너무 쉽네 ㅠ

BC=a,CA=b,AB=c라 하고 A의 이등분선이 EF와 만나는 점이 ACE의 외접원 위에 있음을 보이면 된다. (동일법) 그 점을 K라 하고 A,C,E,K가 한 원 위에 있음을 보이자. 즉 FA \cdot FC = FE \cdot FK임을 보이면 되는데 FA=a+b, FC=a, FE = \sqrt{(a+b)^2+(a+c)^2-(a+b)(a+c)} = \sqrt{a^2 +ab+ac+b^2+c^2-bc} = \sqrt{2a^2 +ab+ac}, FK = FE \cdot \frac{a+b}{2a+b+c}니까 바로 증명끝..

2010 Iran NMO #3

3. 원 W_1,W_2D,P에서 만나고 있다. 점 A,B는 각각 W_1,W_2 위의 점으로 ABW_1,W_2와 동시에 접한다고 한다. DP보다 직선 AB에 더 가깝다고 하자. 직선 AD가 원 W_2C에서 다시 만난다고 할 때, BC의 중점 M에 대해 \angle{DPM}=\angle{BDC}임을 보여라.

의외의 곳에서 반전을 쓰면 의외로 쉽게 풀리기도..

B를 중심으로 반전한다. 그리고 반전된 점들엔 ‘을 붙여서 표현하기로 한다. (점뿐만 아니라 원이나 직선 등등도) 먼적 직선 AB는 그대로 A'B란 직선으로 바뀐다. W_2'A'B와 평행인 어떤 직선이 된다. W_1'은 직선 A'B와는 A'에서 접하는 원으로 W_2'와는 D',P'에서 만난다. 또한 P'BD'보다 더 가까운 거리에 있게 된다. 그러면 C'BA'D'의 외접원이 W_2'와 만나는 점이 되는데 이는 곧 A'BC'D'가 등변사다리꼴이 되게 하는 점이다. 또한 M'BC'=C'M'이 되도록 반직선 B'C'에 존재하는 점.

A'BC'D'는 등변사다리꼴인데 A'D'P'가 이등변삼각형이므로 A'D'=A'P'=BC'=C'M' 이런 변의 관계를 얻는다. 또한 A'BC'P'는 평행사변형이 된다. 따라서 A'B=C'P'이고 A'D' = C'M'이며 \angle D'A'B = \angle C'BA' = \angle M'C'P'이 되어 삼각형 A'BD'C'P'M'이 합동이 된다. 따라서 \angle DPM = \angle DPB + \angle BPM = \angle P'D'B + \angle P'M'B
= \angle A'BD' + \angle P'M'B = \angle M'P'C' + \angle P'M'C' = \angle BC'D' = \angle BDC가 되어 문제가 증명된다.

2010 Iran NMO #2, #6

2010 Iran NMO의 조합 문제 2번과 6번. 놀랍게도 둘 다 기초적인 더블 카운팅 문제였다. 이 중 2번은 올 봄에 있었던 통신강좌 (수행평가라고 이름이 바뀌었던데) 금주의 문제로 나오기도 했다.

2. 평면 위에 n개의 점이 있어 어떤 세 개도 일직선 위에 있진 않다고 한다. 이 때 이 점들 중 세 개를 택하여 만드는 삼각형 중 넓이가 1인 것의 개수는 \frac{2}{3}(n^2-n) 이하임을 보여라.

간단한 더블 카운팅. 집합 {(점 A, (점 B,C)): 삼각형 ABC의 넓이는 1}을 생각한다. 이 집합의 원소의 개수를 센다.
(1) 두 점 B,C를 미리 택하면 삼각형 ABC의 넓이가 1이 되게 하는 A의 자취는 BC에 평행한 직선 두 개이다. 따라서 어떤 세 점도 한 직선 위에 있지 않음에서 그러한 A는 최대 네 개이므로 원소의 개수는 최대 4\binom{n}{2}이다.
(2) 한 편 임의의 넓이가 1인 삼각형 하나에 대해, 그 삼각형이 이 집합에 나오는 가지수는 꼭지점 세 개 중에서 어느 것을 맨 앞에 쓰느냐의 문제이므로 세 번 나온다. 곧, 구하고자 하는 개수를 N이라 하면 원소의 개수는 3N이다.
따라서 이를 연립하면 3N \leq 4\binom{n}{2}이므로 N \leq \frac{2}{3}(n^2-n)이 성립한다.

6. n명의 학생이 있는 한 학교에 몇 가지 특별반이 있다. 각 학생은 자신이 원하는 어떤 특별반에도 개수에 제한 없이 들어갈 수 있다. 모든 특별반은 적어도 2명의 학생이 듣고 있다. 만약 두 개의 서로 다른 특별반이 두 명 이상의 공통 학생을 가지면, 두 특별반의 학생 수는 서로 다르다고 한다. 이 때 특별반의 개수는 (n-1)^2 이하임을 보여라.

약간 어렵지만 그래도 더블 카운팅. 학생 수가 k명인 특별반이 x_k개 있다고 하자. 이 특별반들에 대해 {(특별반, (학생 두 명 A, B)): 특별반에 학생 A,B가 속해 있음}의 원소의 개수를 센다.
(1) 각 특별반은 k명을 가지므로 그 중 두 명을 택하는 가지수는 \binom{k}{2}이다. 곧, 원소의 개수는 x_k\binom{k}{2}이다.
(2) 학생 두 명에 대해 그 둘을 동시에 포함하는 특별반들은 전부 학생 수가 달라야 한다. 곧, 학생 수가 k명이면서 이 둘을 포함하는 특별반은 최대 한 개이므로 원소 개수는 \binom{n}{2}이하이다.
따라서, x_k\binom{k}{2} \leq \binom{n}{2}, 곧 x_k \leq \frac{n(n-1)}{k(k-1)}이다. 따라서 특별반의 개수는 x_2+\cdots+x_n \leq n(n-1) \left( \frac{1}{1 \cdot 2} + \cdots + \frac{1}{(n-1)n} \right) = n(n-1)\left(1-\frac{1}{n} \right) = (n-1)^2이다.

나중에 조합론 2판 쓰게 된다면 추가할 문제.

2010 Iran NMO

2010년 이란 수학 올림피아드 (Iran National Mathematical Olympiad) 문제.

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

2. 평면 위에 n개의 점이 있어 어떤 세 개도 일직선 위에 있진 않다고 한다. 이 때 이 점들 중 세 개를 택하여 만드는 삼각형 중 넓이가 1인 것의 개수는 \frac{2}{3}(n^2-n) 이하임을 보여라.

3. 원 W_1,W_2D,P에서 만나고 있다. 점 A,B는 각각 W_1,W_2 위의 점으로 ABW_1,W_2와 동시에 접한다고 한다. DP보다 직선 AB에 더 가깝다고 하자. 직선 AD가 원 W_2C에서 다시 만난다고 할 때, BC의 중점 M에 대해 \angle{DPM}=\angle{BDC}임을 보여라.

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

5. 삼각형 ABC에서 \angle{A}=\frac{\pi}{3}라 한다. AB,AC의 연장선 위에 E,F를 잡아 BE=CF=BC가 되도록 한다. 직선 EF가 삼각형 ACE의 외접원과 K에서 만난다고 하자. (단, K\neq E) 이 때 K\angle{A}의 이등분선 위에 있음을 보여라.

6. n명의 학생이 있는 한 학교에 몇 가지 특별반이 있다. 각 학생은 자신이 원하는 어떤 특별반에도 개수에 제한 없이 들어갈 수 있다. 모든 특별반은 적어도 2명의 학생이 듣고 있다. 만약 두 개의 서로 다른 특별반이 두 명 이상의 공통 학생을 가지면, 두 특별반의 학생 수는 서로 다르다고 한다. 이 때 특별반의 개수는 (n-1)^2 이하임을 보여라.