Balkan MO 2015

2019. 2. 9. 19:50수학 문풀/기타


문제 링크


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

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

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


스포방지선


















1번 (대수)


그사건...

x=ab2,y=bc2,z=ca2x = ab^2, y = bc^2, z = ca^2으로 치환하면 n=1n = 1 Schur가 된다.

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


2번 (기하)


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

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


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


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

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


EDEDAC,ABAC,AB의 교점을 차례대로 W,ZW,Z라고 하자. Lemma를 반복 적용하면 다음의 사실을 알 수 있다.


M=UVWZM = UV \cap WZ

K=UFWIK = UF \cap WI

L=VFZIL = VF \cap ZI


그런데, UVF\triangle UVFWZI\triangle WZI는 배경의 위치에 있다! 배경의 점은 CC.

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


3번 (조합)


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


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

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

점의 개수는 최소 33673367개임을 보여라.

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


일반화를 위해, 100100대신 NN으로 바꿔서 논증을 진행한다.


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

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


Step 0.

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

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

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


Step 1.

yy축에 평행한 선분이 cc개 있다고 하자. 그리고 그 중 dcd \le c개의 선분이 길이가 1보다 크다.

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


yy축에 평행(세로) : N=x1>x2>>xd>1N = x_1 > x_2 > \cdots > x_d > 1

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


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

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


Step 2.

전체 점의 개수는 x1+x2++xd+cdx_1 + x_2 + \cdots + x_d + c - d이다.


Case 1. c=dc = d

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


점의 개수는 

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

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


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

N=100N = 100에서 이 이차식의 최솟값은 33993399이다.


Case 2. c>dc > d

cc를 포함한 총 d+1d+1개의 정수로 d+1d+1이상의 NdN-d개 정수를 전부 커버하면 된다.


Case 1과 마찬가지로 채우면

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

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

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

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


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


4번 (정수)


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


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


2. Pruning - 

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

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

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

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

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

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


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

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


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


3. 15를 전적으로 믿는다


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


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


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


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


Claim.

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


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


Remark. dn2m2>0dn^2 - m^2 > 0이다.


Case 1. mm55의 배수일 때


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


Case 2. mm55의 배수가 아닐 때


Case 2.1. mm이 짝수


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


- nn이 짝수일 경우

n=2N,m=2Mn = 2N, m = 2M이라고 두자.

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

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

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

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

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


- nn이 홀수인 경우

이 경우는 nn이 짝수인 경우에 포함된다! dn215dn^2 \equiv 15, m24,16m^2 \equiv 4,16. \blacksquare


Case 2.2. mm이 홀수


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