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$