HOP 출제시 유의사항

– 단 문제를 출제할 때에는 반드시 명확한 풀이를 첨부하여 주십시오.

룰북에 명시되어 있는데, 문제 출제시엔 풀이를 꼭 첨부해주세요. 저도 생업에 종사해야 하는지라 하나하나 직접 다 풀어보는 것은 조금 힘듭니다. 감사합니다.

HOP #2

HOP #2 (HOP에 대한 자세한 설명은 설명글을 참조)
기한: 2010년 9월 4일 ~ 2010년 9월 17일 23시 59분

HOP-5. 양의 정수 m,n에 대해 ((x+y)^m-x^m)^n+((x+y)^n-y^n)^m-(x+y)^{mn}의 모든 계수가 0 이상임을 보여라.
Proposed by Sungyoon Kim

HOP-6. 실수 x,y,z \geq 1에 대해 다음 부등식을 증명하여라.
\displaystyle \frac{2}{x+y+z} - \frac{1}{xy+yz+zx} \leq \frac{1}{3}
Proposed by Jihoon Park

HOP-7. 삼각형 ABC의 내심이 I이고 \gamma_1,\gamma_2가 선분 BC, 직선 AI에 접하며 ABC의 외접원과 내접하고 각각 \angle BAI\angle CAI 내부에 놓인다고 한다. \gamma_1,\gamma_2BCD,E에서 접한다고 한다. \displaystyle \frac{AC \cdot BD}{DC} = \frac{AB \cdot CE}{EB}임을 보여라.
Proposed by Sungyoon Kim

HOP-8. 임의의 소수 p와 정수 u,v에 대해 p|uv-n이면 p|f(u)f(v)-m이 성립하는 정수 m,n과 정수 계수 다항식 f를 모두 구하여라.
Proposed by Minki Han

HOP-9. 삼각형 ABC에서 변 AB. AC와 접하고 ABC의 외접원에 내접하는 원을 P_a라 하고. AB,AC와 접하고 ABC의 외접원에 외접하는 원을 Q_a라 하자. 마찬가지로 P_b,P_c,Q_b,Q_c를 정의한다. 이 때 P_a,P_b,P_c의 근심과 Q_a,Q_b,Q_c의 근심을 연결한 선분의 중점은 ABC의 외심임을 보여라.
Proposed by Yoonsuk Seo

HOP #1 Result

HOP-1. 양의 정수 n에 대해, n의 분합이란 x_i \geq 1이며 x_1+\cdots+x_k=n인 정수쌍 (x_1,x_2,\cdots,x_k)를 뜻한다. n을 1보다 큰 홀수로 분합하는 경우의 수를 a_n, n을 2,3,5로 분합하되 x_i=2,x_{i+1}=3i가 존재하지 않는 경우의 수를 b_n이라 하자. a_{n+3}=b_n임을 보여라.
Proposed by Sungyoon Kim

Solution 1. (Official) n+3을 1보다 큰 홀수로 분합한 것에서 1보다 큰 홀수를 2,2,…,2,3로 쓸 수 있다. (2의 개수가 0일 수 있음) 이렇게 변환하면 맨 마지막은 반드시 3이 된다. 역변환도 존재. 즉 a_{n+3}은 n을 2와 3으로 분합한 것의 개수와 같다. 한 편 여기서 2,3이 연속으로 있는 것을 전부 5로 바꾸면 그 결과는 2,3,5로 분합하되 2,3이 연속으로 있는 것이 없는 경우가 된다. 역변환도 존재. 따라서 이 개수는 b_n이 된다.

Comment. 엔스 님의 풀이가 거의 비슷했다.

Solution 2. (블레임) 2,3이 연속으로 나오지 않고 맨 마지막이 2가 아닌 분합의 수를 c_n이라 한다. 이 때 a_n=a_{n-3}+a_{n-5}+\cdots임과 a_{n-2}=a_{n-5}+a_{n-7}+\cdots임에서 a_n=a_{n-2}+a_{n-3}이 된다. (자세한 디테일은 생략. 예컨대 n이 3보다 작다든지 하는 경우) 한 편 b_n=b_{n-2}+b_{n-5}+c_{n-3}이며 (각각 맨 마지막이 2,5,3인 경우) c_n = b_n-b_{n-2}이 되므로 b_n=b_{n-2}+b_{n-3}이 된다. 따라서 a_{n+3},b_n은 같은 점화식을 갖는데 초기항도 세 개 비교하면 같아져서 수학적 귀납법으로 성립한다.

2점: 엔스, 블레임

HOP-2. 임의의 실수 a,b,c \geq 0에 대해 다음 부등식을 증명하여라.
\displaystyle \sum_{cyc} \sqrt{a(a+b)+b(b+c)} \geq 2(a+b+c)
Proposed by Sungyoon Kim

Solution 1. (Official) P_1=b^2+bc+c^2Q_1=bc로 정의하고 비슷하게 P_2,P_3,Q_2,Q_3을 정의한다. 그러면 좌변은 \sum_{cyc} \sqrt{P_3+Q_1}이 된다. 한 편, a,b,c의 크기 순서를 임의로 정할 수는 없지만 a,b,c의 순서롸 P_1,P_2,P_3의 순서가 반대이고 Q_1,Q_2,Q_3도 그렇다. 즉 P_1,P_2,P_3의 순서와 Q_1,Q_2,Q_3의 순서가 같아져서 (P_1+Q_1,P_2+Q_2,P_3+Q_3)(P_3+Q_1,P_1+Q_2,P_2+Q_3)을 majorize한다. 따라서 Karamata 부등식에 의해 f(x)=\sqrt{x}가 오목 함수임에서 (LHS) \geq \sum_{cyc} \sqrt{P_1+Q_1} = \sum_{cyc} (b+c) = (RHS)가 성립한다. 등호 조건은 따져보면 a=b=cb=c=0,c=a=0,a=b=0이 된다. (!)

Solution 2. (블레임) WLOG, a+b+c=1이며 c가 최소값이라 가정하자. 그러면 \sum_{cyc} \sqrt{a^2+b} \geq 2임을 보이면 된다.
먼저 lemma로 x,y,z \geq 0, x,y \leq z이면 \sqrt{x}+\sqrt{y} \geq \sqrt{x+y-z}+\sqrt{z}임을 보인다. 이는 카라마타 부등식으로도 보일 수 있고, 제곱하고 정리한 것이 (x-z)(y-z) \geq 0이 되어 성립하기도 한다. 이 lemma에 의하면 c^2+a \leq (1-c)^2 \Leftrightarrow c \leq ba^2+b \leq (1-c)^2 \Leftrightarrow c \leq a이므로
\sqrt{a^2+b}+\sqrt{c^2+a} \geq \sqrt{a^2+b+c^2+a-(a-c)^2}+1-c = \sqrt{a^2+c}+1-c
가 성립하므로 \sqrt{a^2+c}+\sqrt{b^2+c} \geq 1+c임만 보이면 된다. 이는
(LHS)^2 = a^2+b^2+2c+2\sqrt{(a^2+c)(b^2+c)} \geq a^2+b^2+2c+2(ab+c)
$=a^2+b^2+2ab+4c = (a+b+2c)^2=(a+c)^2$
가 되므로 성립한다. 등호조건은 위와 같다.

2점: 블레임
0점: 조재진
(대칭식이 아니므로 크기 가정을 할 수 없습니다.)

HOP-3. a,b,c는 예각삼각형의 세 변의 길이고 그 외접원의 반지름의 길이는 R이라 한다. 이 때 다음 부등식을 증명하여라.
\displaystyle a^2+b^2+c^2+\frac{abc}{\sqrt{3}R} \geq 4(abc)^{2/3}
Proposed by Sungyoon Kim

Solution 1. (Official) 예각삼각형이므로 Fermat point F는 삼각형 내부에 있다. 그러면 FA=x,FB=y,FC=z라 할 때 a^2=x^2+y^2+xy가 되며 ABC의 넓이인 SS=\frac{abc}{4R}= \frac{\sqrt{3}}{4}(xy+yz+zx)가 되어 \frac{abc}{\sqrt{3}R} = xy+yz+zx가 된다. 이를 이용해서 식을 정리하면 (x^2+y^2+z^2+xy+yz+zx)^3 \geq 8(x^2+xy+y^2)(y^2+yz+z^2)(z^2+zx+x^2)와 동치가 된다. 이거 증명은 그냥 전개했을 때 식이 \sum_{cyc}x^6 + 3\sum_{sym}x^5y + \sum_{cyc}x^4yz \geq 2\sum_{sym}x^4y^2 + \sum_{cyc}x^3y^3 + \sum_{sym}x^3y^2z + 3x^2y^2z^2가 되어 Muirhead 부등식으로 성립한다. 등호는 x=y=z, 즉 ABC가 정삼각형일 때 성립.

Comment. 예각삼각형보다 더 sharp한 조건은, Fermat point가 내부에 있어야 한다는 점에서 ABC의 내각이 전부 120도 이하라는 조건이 된다.

Solution 2. (블레임) 예각삼각형임에서 a^2,b^2,c^2도 삼각형의 세 변을 이룬다. a^2=y+z,b^2=z+x,c^2=x+y라 하자. (x,y,z > 0) 그러면 abc=4RS임을 이용하여 정리하면 좌변은 2(x+y+z) + 2\sqrt{\frac{xy+yz+zx}{3}}이고 우변은 4((x+y)(y+z)(z+x))^{1/3}가 된다. 2로 나누어 세제곱한 식을 증명할 때
9 \left( \sqrt{ \frac{xy+yz+zx}{3} } \right)^3 + (x+y+z)^2 \sqrt{ \frac{xy+yz+zx}{3} } \geq 2(x+y+z)(xy+yz+zx) – A
(x+y+z)^2 \sqrt{\frac{xy+yz+zx}{3}} \geq (x+y+z)(xy+yz+zx) – B
가 산술기하평균 부등식으로 성립한다. 또한
(x+y+z)(x^2+y^2+z^2)+8xyz \geq \frac{17}{9} (x+y+z)(xy+yz+zx) – C
가 전개 후 산술기하평균 부등식과 Schur 부등식으로 성립한다.
\frac{1}{9}A+\frac{26}{9}B란 식과 C 식을 이용하면 원 부등식이 증명된다.

2점: 블레임

HOP-4. x^3+y^4=20을 만족하는 정수 x,y는 존재하지 않음을 증명하여라.
Proposed by Sungyoon Kim

Solution 1. (Official) 정수해가 있다고 가정하고 mod 13으로 보면 좌변은 7이 될 수 없으나 우변은 7이 되어 모순이다.

Comment. 박지훈 님의 풀이가 동일했다.

Solution 2. (jedaihan) 정수해가 있다고 가정하면 x,y는 홀수여야 한다. 그러면 y^4+14^2 = 6^3-x^3=(6-x)(36+6x+x^2)가 된다. 6-x,36+6x+x^2가 둘 다 4k+1 꼴이 될 수 없음은 쉽게 보일 수 있다. 한 편 좌변을 나누는 소수는 14의 소인수이거나 4k+1 꼴의 소수여야 하므로 4k+1 꼴이거나 7이다.
만약 y가 7과 서로 소라면 좌변을 나누는 소인수는 모두 4k+1꼴이 되어 약수가 전부 4k+1 꼴이 된다. 그러나 이는 앞에서 불가능임을 보였으므로 y는 7의 배수이다. 이 때 좌변의 7-지수는 2이다. 만약 6-x,36+6x+x^2 중 단 하나만 7의 배수라면 두 수 모두 4k+1 꼴이 되어 또 모순이다. 따라서 둘 다 7의 배수여야 하는데 이 역시 불가능함을 쉽게 보일 수 있다. 따라서 모순.

Comment. 블레임 님의 풀이가 비슷했다.

2점: 박지훈, 블레임, jedaihan
1점: 페르마
(두 번째 case에서 8-x^3의 임의의 소인수 p를 보는 과정에서 p=3이 될 수도 있습니다.)
0점: 조재진 (세제곱수는 mod 8로 5나 7도 될 수 있습니다.)

현재까지의 총점
박지훈 2 | 블레임 8 | 엔스 2 | 조재진 0 | 페르마 1 | jedaihan 2

다음은 추가된 룰 설명.

– 정답자가 나오지 않는 문제의 경우 Unsolved HOP Problems로 옮겨집니다. 그 문제들의 official solution은 proposer가 따로 부탁하지 않는 한 다른 사람의 풀이가 나올 때까지 공개하지 않는 것으로 합니다.
– 문제의 채점은 대략적으로 이루어지며 문제당 2점 만점으로 합니다.
– 마치 CRUX처럼 적당한 의미를 갖는 conjecture 역시 받습니다.

Unsolved HOP Problems

정답자가 나오지 않는 문제의 경우 Unsolved HOP Problems로 옮겨집니다. 그 문제들의 official solution은 proposer가 따로 부탁하지 않는 한 다른 사람의 풀이가 나올 때까지 공개하지 않는 것으로 합니다.

현재 (2010년 9월 25일) Unsolved Problems list:

HOP-7. 삼각형 ABC의 내심이 I이고 \gamma_1,\gamma_2가 선분 BC, 직선 AI에 접하며 ABC의 외접원과 내접하고 각각 \angle BAI\angle CAI 내부에 놓인다고 한다. \gamma_1,\gamma_2BCD,E에서 접한다고 한다. \displaystyle \frac{AC \cdot BD}{DC} = \frac{AB \cdot CE}{EB}임을 보여라.
Proposed by Sungyoon Kim

HOP-8. 임의의 소수 p와 정수 u,v에 대해 p|uv-n이면 p|f(u)f(v)-m이 성립하는 정수 m,n과 정수 계수 다항식 f를 모두 구하여라.
Proposed by Minki Han

HOP-9. 삼각형 ABC에서 변 AB. AC와 접하고 ABC의 외접원에 내접하는 원을 P_a라 하고. AB,AC와 접하고 ABC의 외접원에 외접하는 원을 Q_a라 하자. 마찬가지로 P_b,P_c,Q_b,Q_c를 정의한다. 이 때 P_a,P_b,P_c의 근심과 Q_a,Q_b,Q_c의 근심을 연결한 선분의 중점은 ABC의 외심임을 보여라.
Proposed by Yoonsuk Seo

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}로 옮겨지는 과정에서 역시 모든 홀수가 나온다. 끝

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