2019. 2. 9. 19:50ㆍ수학 문풀/기타
재활을 위해 IMO보다 부담 없이 건드려볼 수 있는 셋을 선택한다고 했는데... 아직 나한텐 너무 어렵다.
문제 셋은 굉장히 좋다. 고인물 테크닉을 요구하지도 않고.
나는 4번만 풀이를 봤고, 123은 혼자서 풀었다.
스포방지선
1번 (대수)
그사건...
으로 치환하면 Schur가 된다.
어차피 부등식은 이제 나오지 않으니 던져버리자!
2번 (기하)
지오지브라의 힘을 빌렸다. 점을 몇 개 더 잡지만 저 그림을 지워버린 관계로 말로 때우자.
잘 그린 그림으로부터, , , 가 한 점에서 만난다는 것을 알 수 있다.
Lemma) , 라고 하면 는 collinear하다.
파스칼의 육각형 정리에 의해서 collinear는 바로 나온다.
이제 만 보이면 충분한데, 가 concyclic인 걸 이용하면 각돌리기로 쉽게 보일 수 있다.
와 의 교점을 차례대로 라고 하자. Lemma를 반복 적용하면 다음의 사실을 알 수 있다.
그런데, 와 는 배경의 위치에 있다! 배경의 점은 .
따라서 데자르그의 정리에 의해 은 collinear하다.
3번 (조합)
문제를 다음과 같이 바꿀 수 있다.
2차원 격자판 위에 점들을 겹치지 않게 놓는다.
모든 에 대해 크기 의 이나 의 점집합이 존재할 때,
점의 개수는 최소 개임을 보여라.
일단 은 의 냄새가 굉장히 강하게 난다. 밀고 가 보자.
일반화를 위해, 대신 으로 바꿔서 논증을 진행한다.
조건을 만족하는 최소 개수의 점 배열을 생각하자. 이 배열에는 길이 짜리 선분(점의 1차원적 나열)이 존재한다.
일반성을 잃지 않고, 이 선분이 축에 평행하게 놓여 있다고 하자.
Step 0.
축에 평행하게 놓인 모든 선분을 내림차순으로 정렬하고, 시작점을 으로 두어도 아무 문제가 생기지 않는다.
이 형태를 갖추지 않은 최적해가 존재하면 개수를 늘리지 않고 이 형태로 만들 수 있다.
길지 않게 얘기하자면, 에 대칭시킨 후 정렬을 한 번 더 하면 된다.
Step 1.
축에 평행한 선분이 개 있다고 하자. 그리고 그 중 개의 선분이 길이가 1보다 크다.
이를 가정하면, 축에 평행한 모든 선분의 크기들을 다음과 같이 나열할 수 있다.
축에 평행(세로) :
축에 평행(가로) :
Note. 이 성립하는 이유를 언급하지 않았다.
간단하다. 이면 번째에서 가장 위의 점을 들어내도 문제가 생기지 않는다.
Step 2.
전체 점의 개수는 이다.
Case 1.
이 경우 들이 이상의 정수를 전부 커버해야 한다. 까지 우겨넣고, 나머지는 부터 그리디하게 채운다.
점의 개수는
더하기,
이다.
전개하면 식은 이고,
에서 이 이차식의 최솟값은 이다.
Case 2.
를 포함한 총 개의 정수로 이상의 개 정수를 전부 커버하면 된다.
Case 1과 마찬가지로 채우면
.
이다.
전개한 식은 이고,
에서 이 이차식의 최솟값은 이다.
일반식 찾으려다가 귀찮아서 안했다 >_______<
4번 (정수)
이 셋을 통틀어서 제일 갓문제라고 생각한다.
1. 킹리적 갓심 - 20개 중에 하나를 잡으라고 했으니까, 대충 꼴을 잡으면 되지 않을까?
2. Pruning -
제곱수를 포함하는 mod (0,1,4,5,9,16)들을 전부 제거한다.
10 이하의 mod들은 에서 막힌다.
후보는 11, 12, 13, 14, 15, 17, 18, 19.
이고, 이므로 정수부가 17, 18, 19도 에서 막힌다.
이고, 이므로 11, 12도 에서 막힌다.
좀 더 공들여서 계산하면 13도 에서 막힌다.
가능한 놈은 14, 15뿐이다.
14는 손계산으로는 힘들다. 가장 작은 반례가 무려 쯤 가야 나온다.
어쨌든 결론부터 얘기하자면. 15는 된다.
3. 15를 전적으로 믿는다
15가 될 것 같다는 킹리적 갓심이 들었다면, 멋진 관찰을 얹어서 마무리하자.
Lemma. .
식을 왼쪽으로 넘기면 가 나와서 완전제곱식으로 증명이 끝난다. 두 값의 차이가 보다 작거나 같음에 주목하자. 매우 좋은 근사임을 알 수 있다.
를 넣고, 로 두자. 그렇다면 우리가 보일 식은
Claim.
이제는 그냥 정수론 문제다. 난 여기서부터 솔루션을 보지 않고 혼자 했다. 계산이 더러울 수 있으니 여기서부터는 혼자 풀거나, 오피셜 풀이를 참조하자.
Remark. 이다.
Case 1. 이 의 배수일 때
가 5의 배수이므로 이 식은 꼴로 묶인다. 이므로 이 값은 5 이상이다.
Case 2. 이 의 배수가 아닐 때
Case 2.1. 이 짝수
이 경우 만 가능하다.
- 이 짝수일 경우
이라고 두자.
이므로, 만 보이면 충분하다.
이려면 의 기우성이 달라야 한다.
이 짝수라면 이므로 모순. 따라서 이 홀수고 이 짝수다.
그런데 은 5의 배수일 수 없으므로, 으로 가능한 값은 뿐이다.
이므로 불가능!
- 이 홀수인 경우
이 경우는 이 짝수인 경우에 포함된다! , .
Case 2.2. 이 홀수
이 경우 , 이므로 4가지 중 어느 경우도 차이가 5보다 작을 수 없다.
'수학 문풀 > 기타' 카테고리의 다른 글
KAIST POW 2019-03 Simple Spectrum (0) | 2019.03.29 |
---|---|
KAIST POW 2019-02 Simplification of an expression with factorials (0) | 2019.03.29 |
Putnam 2017 풀이 - 풀리는 것만 (0) | 2018.11.30 |
2018 대수경 2분야 5번 풀이 (0) | 2018.11.24 |
2017 Benelux MO 풀이 (0) | 2018.09.29 |