Balkan MO 2015

문제 링크

재활을 위해 IMO보다 부담 없이 건드려볼 수 있는 셋을 선택한다고 했는데... 아직 나한텐 너무 어렵다.

문제 셋은 굉장히 좋다. 고인물 테크닉을 요구하지도 않고.

나는 4번만 풀이를 봤고, 123은 혼자서 풀었다.

---

스포방지선

---

1번 (대수)

그사건...

\(x = ab^2, y = bc^2, z = ca^2\)으로 치환하면 \(n = 1\) Schur가 된다.

어차피 부등식은 이제 나오지 않으니 던져버리자!

2번 (기하)

지오지브라의 힘을 빌렸다. 점을 몇 개 더 잡지만 저 그림을 지워버린 관계로 말로 때우자.

잘 그린 그림으로부터, \(MI (\parallel AB)\), \(AC\), \(EF\)가 한 점에서 만난다는 것을 알 수 있다.

Lemma) \(U = EF \cap AC\), \(V = DE \cap BC\)라고 하면 \((M,U,I,V)\)는 collinear하다.

파스칼의 육각형 정리에 의해서 \((U,I,V)\) collinear는 바로 나온다.

이제 \(UV \parallel AB\)만 보이면 충분한데, \((I,V,D,C)\)가 concyclic인 걸 이용하면 각돌리기로 쉽게 보일 수 있다.

\(ED\)와 \(AC,AB\)의 교점을 차례대로 \(W,Z\)라고 하자. Lemma를 반복 적용하면 다음의 사실을 알 수 있다.

\(M = UV \cap WZ\)

\(K = UF \cap WI\)

\(L = VF \cap ZI\)

그런데, \(\triangle UVF\)와 \(\triangle WZI\)는 배경의 위치에 있다! 배경의 점은 \(C\).

따라서 데자르그의 정리에 의해 \(K,L,M\)은 collinear하다. \(\blacksquare\)

3번 (조합)

문제를 다음과 같이 바꿀 수 있다.

2차원 격자판 위에 점들을 겹치지 않게 놓는다.

모든 \(n = 1..100\)에 대해 크기 \(n\)의 \(\{(x,*)\}\)이나 \(\{(*,y)\}\)의 점집합이 존재할 때,

점의 개수는 최소 \(3367\)개임을 보여라.

일단 \(3367\)은 \(x(x+1)/3\)의 냄새가 굉장히 강하게 난다. 밀고 가 보자.

일반화를 위해, \(100\)대신 \(N\)으로 바꿔서 논증을 진행한다.

조건을 만족하는 최소 개수의 점 배열을 생각하자. 이 배열에는 길이 \(N\)짜리 선분(점의 1차원적 나열)이 존재한다.

일반성을 잃지 않고, 이 선분이 \(y\)축에 평행하게 놓여 있다고 하자.

Step 0.

\(y\)축에 평행하게 놓인 모든 선분을 내림차순으로 정렬하고, 시작점을 \(y = 0\)으로 두어도 아무 문제가 생기지 않는다.

이 형태를 갖추지 않은 최적해가 존재하면 개수를 늘리지 않고 이 형태로 만들 수 있다. 

길지 않게 얘기하자면, \(y = x\)에 대칭시킨 후 정렬을 한 번 더 하면 된다.

Step 1.

\(y\)축에 평행한 선분이 \(c\)개 있다고 하자. 그리고 그 중 \(d \le c\)개의 선분이 길이가 1보다 크다.

이를 가정하면, \(x,y\)축에 평행한 모든 선분의 크기들을 다음과 같이 나열할 수 있다.

\(y\)축에 평행(세로) : \(N = x_1 > x_2 > \cdots > x_d > 1\)

\(x\)축에 평행(가로) : \(1,2, \cdots d, c\)

Note. \(x_i > x_{i+1}\)이 성립하는 이유를 언급하지 않았다.

간단하다. \(x_i = x_{i+1}\)이면 \(i+1\)번째에서 가장 위의 점을 들어내도 문제가 생기지 않는다.

Step 2.

전체 점의 개수는 \(x_1 + x_2 + \cdots + x_d + c - d\)이다.

Case 1. \(c = d\)

이 경우 \(x_{i}\)들이 \(d+1\) 이상의 정수를 전부 커버해야 한다. \(N \cdots d+1\)까지 우겨넣고, 나머지는 \(2\)부터 그리디하게 채운다.

점의 개수는 

\(N + (N-1) + \cdots + (d+1) = (N(N+1) - d(d+1))/2\) 더하기,

\(2 + 3 + \cdots + (2d-N+1)\)이다.

전개하면 식은 \(\frac{1}{2}(3d^2 + (5-4N)d + 2N^2 - 2N)\)이고,

\(N = 100\)에서 이 이차식의 최솟값은 \(3399\)이다.

Case 2. \(c > d\)

\(c\)를 포함한 총 \(d+1\)개의 정수로 \(d+1\)이상의 \(N-d\)개 정수를 전부 커버하면 된다.

Case 1과 마찬가지로 채우면

\(N + (N-1) + \cdots + (d+1) = (N(N+1) - d(d+1))/2\).

\(2 + 3 + \cdots + (2d-N+2) - d\)이다.

전개한 식은 \(\frac{1}{2}(3d^2 + (7-4N)d + 2N^2 - 4N + 4)\)이고,

\(N = 100\)에서 이 이차식의 최솟값은 \(3367\)이다. \(\blacksquare\)

일반식 찾으려다가 귀찮아서 안했다 >_______<

4번 (정수)

이 셋을 통틀어서 제일 갓문제라고 생각한다.

1. 킹리적 갓심 - 20개 중에 하나를 잡으라고 했으니까, 대충 \(20k + a\)꼴을 잡으면 되지 않을까?

2. Pruning - 

제곱수를 포함하는 mod (0,1,4,5,9,16)들을 전부 제거한다. 

10 이하의 mod들은 \(k = 1\)에서 막힌다.

후보는 11, 12, 13, 14, 15, 17, 18, 19.

\(4.5^2 = 20.25\)이고, \(4.5 \times 0.5 \le 2.5\)이므로 정수부가 17, 18, 19도 \(k = 1\)에서 막힌다.

\(3.6^2 = 12.96\)이고, \(3.6 \times 0.6 \le 2.5\)이므로 11, 12도 \(k = 1\)에서 막힌다.

좀 더 공들여서 계산하면 13도 \(k = 1\)에서 막힌다.

가능한 놈은 14, 15뿐이다.

14는 손계산으로는 힘들다. 가장 작은 반례가 무려 \(5\sqrt{74} \times \{ 5\sqrt{74} \} = 0.50006...\)쯤 가야 나온다.

어쨌든 결론부터 얘기하자면. 15는 된다.

3. 15를 전적으로 믿는다

15가 될 것 같다는 킹리적 갓심이 들었다면, 멋진 관찰을 얹어서 마무리하자.

Lemma. \(x\{x \} \ge (x^2 - [x]^2)/2\).

식을 왼쪽으로 넘기면 \((x-[x])^2/2\)가 나와서 완전제곱식으로 증명이 끝난다. 두 값의 차이가 \(0.5\{x\}^2\)보다 작거나 같음에 주목하자. 매우 좋은 근사임을 알 수 있다.

\(x = n\sqrt{d}\)를 넣고, \(m = [x]\)로 두자. 그렇다면 우리가 보일 식은

Claim.

$$ \frac{dn^2-m^2}{2} \ge \frac{5}{2} \implies dn^2 - m^2 \ge 5 $$

이제는 그냥 정수론 문제다. 난 여기서부터 솔루션을 보지 않고 혼자 했다. 계산이 더러울 수 있으니 여기서부터는 혼자 풀거나, 오피셜 풀이를 참조하자.

Remark. \(dn^2 - m^2 > 0\)이다.

Case 1. \(m\)이 \(5\)의 배수일 때

\(d\)가 5의 배수이므로 이 식은 \(5(x-y)\)꼴로 묶인다. \(x > y\)이므로 이 값은 5 이상이다. \(\blacksquare\)

Case 2. \(m\)이 \(5\)의 배수가 아닐 때

Case 2.1. \(m\)이 짝수

이 경우 \(m^2 \equiv 4, 16 (\text{mod } 20)\)만 가능하다.

- \(n\)이 짝수일 경우

\(n = 2N, m = 2M\)이라고 두자.

\(dn^2 - m^2 = 4(dN^2 - M^2)\)이므로, \(dN^2 - M^2 > 1\)만 보이면 충분하다.

\(dN^2 - M^2 = 1\)이려면 \(N,M\)의 기우성이 달라야 한다.

\(N\)이 짝수라면 \(M^2 \equiv 3 (\text{mod } 4)\)이므로 모순. 따라서 \(N\)이 홀수고 \(M\)이 짝수다.

그런데 \(M\)은 5의 배수일 수 없으므로, \(M^2\text{mod }20\)으로 가능한 값은 \(4,16\)뿐이다.

\(dN^2 \equiv 15(\text{mod }20)\)이므로 불가능! \(\blacksquare\)

- \(n\)이 홀수인 경우

이 경우는 \(n\)이 짝수인 경우에 포함된다! \(dn^2 \equiv 15\), \(m^2 \equiv 4,16\). \(\blacksquare\)

Case 2.2. \(m\)이 홀수

이 경우 \(dn^2 \equiv 0,15\), \(m^2 \equiv 1,9\)이므로 4가지 중 어느 경우도 차이가 5보다 작을 수 없다.\(\blacksquare\)