1. 개요
역대 국제수학올림피아드에 수록됐던 문제들 중 악랄한 난제라고 여겨지는 것들을 모은 문서이다. 어느 국제 올림피아드가 안 그렇겠냐만, 영재 중의 영재들인 국제 올림피아드 참가자들에게도 풀기가 매우 힘든 문제가 잊을 때마다 한 번씩은 나온다. 특히 IMO는 국제 올림피아드 중에서 역사가 가장 오래되었으며 가장 유명하기 때문에 난제의 악명이 널리 알려져 있다.2. 난제 목록
예전 IMO 기출문제들은 여기서 볼 수 있다. 공식 한국어 번역본이 없는 경우에는 여기를 참고.풀이들을 보고 싶다면 여기[1]와 여기를 참고.
2.1. IMO 1988 P6
Problem 6
Let [math(a)] and [math(b)] be positive integers such that [math(ab+1)] divides [math(a^2+b^2)]. Show that
{{{#!wiki style="text-align: center"
Let [math(a)] and [math(b)] be positive integers such that [math(ab+1)] divides [math(a^2+b^2)]. Show that
{{{#!wiki style="text-align: center"
[math(\dfrac{a^2+b^2}{ab+1})]}}}
is the square of an integer.
문제 6
[math(a)]와 [math(b)]는 자연수이고 [math(a^2+b^2)]은 [math(ab+1)]로 나누어떨어진다. [math(\dfrac{a^2+b^2}{ab+1})]은 완전제곱수임을 보여라.
[math(a)]와 [math(b)]는 자연수이고 [math(a^2+b^2)]은 [math(ab+1)]로 나누어떨어진다. [math(\dfrac{a^2+b^2}{ab+1})]은 완전제곱수임을 보여라.
지금까지도 역대 IMO 문제 중 가장 극악의 난이도를 가진 문제였다고 회자된다. 이 문제가 얼마나 악명이 높냐면, 대회 이전 예행연습격으로 교수들에게 이 문제를 풀게 했는데, 6시간 동안 단 한 명도 풀지 못했다고 한다.
2.1.1. 풀이
Vieta jumping이라는 귀류법과 비에트의 정리를 기반으로 한 증명이 이 문제의 가장 정석적이고 깔끔한 풀이로 알려져 있다. 문제 6에 Vieta jumping을 적용하면 다음과 같다.여담으로 임의의 자연수 [math(n)]에 대하여 [math(\dfrac{a^2+b^2}{ab+1}=n^2)]이라고 할때 [math(a=n^3, b=n)]이다.
- [풀이]
- ----
먼저, 귀류법을 사용하여 양수인 제곱근을 가지지 않는 [math(k)]를 설정하고 [math(k=\dfrac{a^2+b^2}{ab+1})]를 만족시키는 양수 [math((a,b))]가 있다고 가정하자.
[math(k=\dfrac{a^2+b^2}{ab+1})]에서 [math(a+b)]가 최솟값임을 만족시키는 양수 [math((A,B))]를 가정하고 일반성을 잃지 않고[2] [math(A\ge B)]라고 추가로 놓자.
합동식의 정의에서 알 수 있듯이 [math(a=kx-b\equiv b\pmod x)]를 상기하고, 임의의 변수 [math(x)]를 이용해 [math(A)]를 [math(B)]로 다음과 치환하면,
[math(x^2-(kB)x+(B^2-k)=0)]
위 방정식의 한 근 [math(x_1)]가 [math(A)]임이 쉽게 확인되고, 비에트의 정리에 의해서 다른 근이 [math(x_2=kB-A,x_2=\dfrac{B^2-k}{A})]임을 확인할 수 있다.
[math(x_2)]에 대한 첫 번째 풀이는 [math(x_2)]가 정수임을 보여주는 반면, 두 번째 풀이는 [math(k)]가 양수 제곱근이 되지 않는 [math(x_2\ne 0)]을 만족시킴을 보여준다. 또한, [math(\dfrac{{x_2}^2+{B}^2}{{x_2}B+1}=k>0)]로부터 [math(x_2)]가 양수임을 추가적으로 보이므로, [math(A\ge B)]가 [math(x_2=\dfrac{B^2-k}{A}<A)]임을 상기하면, [math(x_2+B<A+B)]로써 [math(A+B)]가 최솟값을 갖는 가정에 대한 모순이다.
풀이 영상
2.2. IMO 2011 P2
Problem 2
Let [math(\cal S)] be a finite set of at least two points in the plane. Assume that no three points of [math(\cal S)] are collinear. A windmill is a process that starts with a line [math(\ell)] going through a single point [math(P\in\cal S)]. The line rotates clockwise about the pivot [math(P)] until the first time that the line meets some other point belonging to [math(\cal S)]. This point, [math(Q)], takes over as the new pivot, and the line now rotates clockwise about [math(Q)], until it next meets a point of [math(\cal S)]. This process continues indefinitely.
Show that we can choose a point [math(P)] in [math(\cal S)] and a line [math(\ell)] going through [math(P)] such that the resulting windmill uses each point of [math(\cal S)] as a pivot infinitely many times.
Let [math(\cal S)] be a finite set of at least two points in the plane. Assume that no three points of [math(\cal S)] are collinear. A windmill is a process that starts with a line [math(\ell)] going through a single point [math(P\in\cal S)]. The line rotates clockwise about the pivot [math(P)] until the first time that the line meets some other point belonging to [math(\cal S)]. This point, [math(Q)], takes over as the new pivot, and the line now rotates clockwise about [math(Q)], until it next meets a point of [math(\cal S)]. This process continues indefinitely.
Show that we can choose a point [math(P)] in [math(\cal S)] and a line [math(\ell)] going through [math(P)] such that the resulting windmill uses each point of [math(\cal S)] as a pivot infinitely many times.
문제 2
평면 위의 두 개 이상의 유한 개의 점으로 이루어진 집합 [math(\cal S)]가 있다. 이 집합의 어느 세 점도 일직선 위에 있지 않다. 풍차란 다음과 같은 과정을 의미한다: [math(\cal S)] 중의 단 한 점 [math(P)]를 지나는 직선 [math(\ell)]로부터 시작하여, [math(P)]를 회전의 중심으로 하여 [math(\ell)]을 시계방향으로 회전시키다가 이 직선이 처음으로 [math(\cal S)]에 속하는 다른 점 [math(Q)]를 만나면, 다시 [math(Q)]를 새로운 회전중심으로 하여 시계방향으로 회전을 계속 진행한다. 이러한 진행을 [math(\cal S)]의 점들을 회전중심으로 하여 무한 번 계속한다.
적당한 [math(P\in\cal S)]와 이 점을 지나는 적당한 직선 [math(\ell)]을 선택하여 이로부터 시작된 풍차가 [math(\cal S)]의 모든 점들을 회전중심으로 무한히 사용하게 할 수 있음을 보여라.
평면 위의 두 개 이상의 유한 개의 점으로 이루어진 집합 [math(\cal S)]가 있다. 이 집합의 어느 세 점도 일직선 위에 있지 않다. 풍차란 다음과 같은 과정을 의미한다: [math(\cal S)] 중의 단 한 점 [math(P)]를 지나는 직선 [math(\ell)]로부터 시작하여, [math(P)]를 회전의 중심으로 하여 [math(\ell)]을 시계방향으로 회전시키다가 이 직선이 처음으로 [math(\cal S)]에 속하는 다른 점 [math(Q)]를 만나면, 다시 [math(Q)]를 새로운 회전중심으로 하여 시계방향으로 회전을 계속 진행한다. 이러한 진행을 [math(\cal S)]의 점들을 회전중심으로 하여 무한 번 계속한다.
적당한 [math(P\in\cal S)]와 이 점을 지나는 적당한 직선 [math(\ell)]을 선택하여 이로부터 시작된 풍차가 [math(\cal S)]의 모든 점들을 회전중심으로 무한히 사용하게 할 수 있음을 보여라.
| 당시 한국 대표단의 성적을 보면 난이도가 얼마나 극랄했는지 짐작할 수 있다.[3] |
학부 수준 수학을 다루는 수학 유튜버 3Blue1Brown이 거의 유일하게 다룬 IMO 문제이다. 사실, 정수, 기하에서나 다룰법한 문제들이 비중을 차지하는 IMO에서 해석학적인 추론을 요하는 문제는 엄청나게 흔치 않다.
2.2.1. 풀이
- [풀이]
- ----
먼저, 집합 [math(\cal S)]의 원소의 개수를 [math(N)]이라 한 뒤, 모든 원소가 각기 다른 [math(x)] 좌표를 가지도록 하는 좌표계를 가정하자. (임의의 두 원소를 이은 직선의 개수가 [math(\frac{N(N-1)}2)]로 유한하므로, 이 직선들과 y축의 방향이 다르게 잡으면 된다.) 그러면 [math(x_1<x_2<\cdots<x_N)]을 따르는 [math(x)]의 좌표의 증가에 따라서 집합 [math(\cal S)]의 [math(P)]의 좌표의 수를 수치화할 수 있다.
집합 [math(\cal S)]를 각각 절반으로 나눈 뒤, 임의의 자연수 [math(n)]이 [math(N=2n+1+d)] (N이 홀수라면 d=0, N이 짝수라면 d=1)에 따라서 각각 홀수 짝수가 되는 지점을 정의할 수 있다.
직선 [math(\ell)]이 [math(P_{n+1})]을 수직으로 통과하는 기점으로 windmill 과정을 시작하자. 직선의 방향벡터에 따른 증가 방향과 감소 방향은 좌표계를 각각 색상으로 표시할 수 있는데, 직선 [math(\ell)]의 왼쪽, 오른쪽 부분은 청색과 갈색으로, 회전 중심 지점은 흰색으로 두면, [math(n)]개의 청색 지점들과 하나의 흰색 지점, [math(n+d)]개의 갈색 지점을 얻을 수 있다.
이제 180도로 windmill을 하면, 직선의 방향벡터가 반대로 바뀌는데, 청색이었던 작은 [math(x)] 좌표값들이 회전된 직선 [math(\ell)]의 오른쪽에 오면서, 갈색으로 바뀐다. 반대의 경우도 마찬가지로, 큰 [math(x)] 좌표값들이 회전함으로써, 청색으로 바뀐다.
회전 중심 지점이 바뀐다는 것을 다시 한번 상기하자면, 이전 회전 중심은 새로운 회전 중심이 생기는 선과 같은 부분에 위치하게 된다. 즉, windmill이 지속되는 동안, 청색 지점과 갈색 지점의 수가 일정하게 유지된다. 그러므로 회전 지점은 [math(P_{n+d})]이다.
게다가 windmill 과정이 시작된 후에 모든 청색과 갈색 부분의 교환을 상기하면, 모든 지점이 회전의 한 부분에서 회전 중심이 되었음을 알 수 있다.
그러므로, 모든 windmill의 180도 회전에서 같은 현상이 지속되고, 무한의 회전은 무한의 색상 변경이 되며, 이는 각 점이 무한히 많은 횟수만큼 회전중심이 된다는 의미가 되므로 문제가 참임이 증명된다.
2.3. IMO 2017 P3
Problem 3
A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, [math(A_0)], and the hunter's starting point, [math(B_0)], are the same. After [math(n-1)] rounds of the game, the rabbit is at point [math(A_{n-1})] and the hunter is at point [math(B_{n-1})]. In the [math(n)]th round of the game, three things occur in order.
I. The rabbit moves invisibly to a point [math(A_n)] such that the distance between [math(A_{n-1})] and [math(A_n)] is exactly [math(1)].
I. A tracking device reports a point [math(P_n)] to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between [math(P_n)] and [math(A_n)] is at most [math(1)].
I. The hunter moves visibly to a point [math(B_n)] such that the distance between [math(B_{n-1})] and [math(B_n)] is exactly [math(1)].
Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after [math({10}^9)] rounds she can ensure that the distance between her and the rabbit is at most [math(100)]?
A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, [math(A_0)], and the hunter's starting point, [math(B_0)], are the same. After [math(n-1)] rounds of the game, the rabbit is at point [math(A_{n-1})] and the hunter is at point [math(B_{n-1})]. In the [math(n)]th round of the game, three things occur in order.
I. The rabbit moves invisibly to a point [math(A_n)] such that the distance between [math(A_{n-1})] and [math(A_n)] is exactly [math(1)].
I. A tracking device reports a point [math(P_n)] to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between [math(P_n)] and [math(A_n)] is at most [math(1)].
I. The hunter moves visibly to a point [math(B_n)] such that the distance between [math(B_{n-1})] and [math(B_n)] is exactly [math(1)].
Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after [math({10}^9)] rounds she can ensure that the distance between her and the rabbit is at most [math(100)]?
문제 3
한 사냥꾼과 보이지 않는 토끼 한 마리가 평면 상에서 다음과 같은 게임을 한다. 토끼의 출발점 [math(A_0)]와 사냥꾼의 출발점 [math(B_0)]는 일치한다. 게임의 [math(n−1)]번째 라운드를 마친 후 토끼가 위치한 점을 [math(A_{n−1})], 사냥꾼이 위치한 점을 [math(B_{n−1})]이라 하자. [math(n)]번째 라운드에서 다음과 같은 세 가지가 순차적으로 발생한다.
I. 토끼가 보이지 않게 점 [math(A_n)]으로 움직이고, [math(A_{n−1})]과 [math(A_n)]의 거리는 정확히 [math(1)]이다.
I. 사냥꾼의 추적기가 점 [math(P_n)]의 위치를 알려준다. 이 추적기가 알려주는 점 [math(P_n)]과 [math(A_n)]의 거리는 [math(1)] 이하임이 보장될 뿐이다.
I. 사냥꾼은 눈에 띄게 점 [math(B_n)]으로 움직이고, [math(B_{n−1})]과 [math(B_n)]의 거리는 정확히 [math(1)]이다.
토끼가 어떻게 움직이든, 추적기가 어떤 점을 알려주든 상관없이 항상 사냥꾼이 [math({10}^9)] 라운드 후에 그와 토끼의 거리가 [math(100)] 이하가 되도록 할 수가 있겠는가?
한 사냥꾼과 보이지 않는 토끼 한 마리가 평면 상에서 다음과 같은 게임을 한다. 토끼의 출발점 [math(A_0)]와 사냥꾼의 출발점 [math(B_0)]는 일치한다. 게임의 [math(n−1)]번째 라운드를 마친 후 토끼가 위치한 점을 [math(A_{n−1})], 사냥꾼이 위치한 점을 [math(B_{n−1})]이라 하자. [math(n)]번째 라운드에서 다음과 같은 세 가지가 순차적으로 발생한다.
I. 토끼가 보이지 않게 점 [math(A_n)]으로 움직이고, [math(A_{n−1})]과 [math(A_n)]의 거리는 정확히 [math(1)]이다.
I. 사냥꾼의 추적기가 점 [math(P_n)]의 위치를 알려준다. 이 추적기가 알려주는 점 [math(P_n)]과 [math(A_n)]의 거리는 [math(1)] 이하임이 보장될 뿐이다.
I. 사냥꾼은 눈에 띄게 점 [math(B_n)]으로 움직이고, [math(B_{n−1})]과 [math(B_n)]의 거리는 정확히 [math(1)]이다.
토끼가 어떻게 움직이든, 추적기가 어떤 점을 알려주든 상관없이 항상 사냥꾼이 [math({10}^9)] 라운드 후에 그와 토끼의 거리가 [math(100)] 이하가 되도록 할 수가 있겠는가?
2.3.1. 풀이
- [풀이]
- ----
정답은 ‘그렇게 할 수 없다.’이다.
귀류법으로, 문제의 조건을 만족시키는 전략 [math(f)]가 존재한다고 가정하자. 매 라운드마다 사냥꾼은 전략 [math(f)]와 주어진 정보에 따라 [math(B_n=f(B_{n-1}, P_1, P_2, \cdots, P_{n}))]으로 움직인다. 사냥꾼의 이동에 확률적인 요소가 개입될 수도 있으나, 문제의 조건을 만족하려면 토끼, 추적기뿐만 아니라 이 확률적인 요소까지 _최악의 경우_를 상정하더라도 반드시 [math({10}^9)] 라운드 후에 사냥꾼과 토끼의 거리가 [math(100)] 이하가 되어야 한다.
처음에 토끼가 [math(A_1)]으로 움직이고 추적기가 원점인 [math(A_0)]을 알려주는 경우, 사냥꾼은 정보가 전혀 없는 상태에서 [math(1)]만큼 이동해야 한다. 최악의 경우 토끼와 정반대로 이동해서 [math(B_1A_1=2)]가 될 것이다.
이제 토끼는 [math(A_1)]에서 [math(A_{201})]까지 같은 방향으로 200회 움직이며, 그 방향은 [math(\overrightarrow{B_1A_1})]의 방향에서 딱 [math(\pm arcsin(1/200))]만큼 어긋난 방향이다. 추적기가 알려주는 [math(P_2, P_3, \cdots, P_{201})]는 [math(A_2, A_3,\cdots, A_{201})]에서 [math(\overrightarrow{B_1A_1})]에 내린 수선의 발이다. 그림을 그려 보면 [math(AP)]가 점점 증가하다가 [math(A_{201}P_{201})]에서 [math(1)]이 되는 것을 알 수 있다.
요점은, 어긋난 방향의 부호에 따라 [math(A_{201})]의 후보가 2개가 되는데, 어느 쪽이든 추적기가 알려주는 [math(P_2, P_3, \cdots, P_{201})]은 동일하다는 것이다. 사냥꾼도 200 라운드 동안 움직여서 [math(B_{201})]에 도달했으나, 재수없게도 [math(B_{201})]에서 보다 멀리 떨어진 후보로 토끼가 움직였던 것이다. [math(B_{201})]은 중심이 [math(B_1)]이고 반지름이 [math(200)]인 원 안에 존재하는데, [math(\overrightarrow{B_1A_1})]을 따라 [math(200)]만큼 움직인 점이 두 후보 모두와의 거리가 최소가 된다.
이 때 거리의 제곱의 변화를 관찰하면 [math({B_{201}A_{201}}^2=(B_1A_1+\sqrt{200^2-1}-200)^2+1)]이 되는데,
[math(2 \leq B_1A_1 \leq 100)]라는 가정 하에 잘 계산하면 [math({B_{201}A_{201}}^2 \geq {B_1A_1}^2+1/2)]를 얻는다.
매 200 라운드마다 사냥꾼이 토끼를 바라본 방향과 [math(\pm\arcsin(1/200))]만큼 어긋난 방향으로 토끼가 200회 이동하면, 최악의 경우 거리의 제곱이 [math(1/2)] 이상 증가한다. 이를 반복하면, 많아도 [math(4 \times 10^6+1)] 라운드 후에 거리가 [math(100)]을 넘어서게 된다. 그 이후에는 토끼가 사냥꾼과 정반대로 도망치기만 해도 거리를 좁힐 수가 없다. 따라서 전략 [math(f)]가 문제의 조건을 만족한다는 가정에 모순되므로 증명이 완료되었다.
[1] 단, 2003년까지만 있다.[2] Without loss of generality. 증명과정에서 여러 변수의 크기 비교가 중요할 때가 있고, 또 해당 변수들의 위치를 바꾸어도 증명 과정이 달라지지 않는 경우가 있다. 이럴 경우 서로간의 크기를 케이스별로 분류한 뒤 같은 증명을 여러 번 하는 시간낭비를 방지하기 위해 변수들 중 어느 것이 가장 크고, 어느 것이 가장 작고... 이렇게 변수들간의 크기를 미리 정해 놓고 해당 케이스 하나만 증명하고자 할 때 사용한다. 왜냐하면 변수를 적당히 바꾸면 미리 정해둔 순서로 만들어낼 수 있기 때문이다. 이 문제의 경우 A가 B보다 크거나 같다고 일단 정해 놓는 것이다. 왜냐하면 B가 A보다 클 경우 A와 B를 서로 바꾸더라도 달라질 게 없기 때문이다.[3] 출처