1999 아시아태평양수학올림피아드 5번문제

집합 $S$는 평면 상의 $2n+1$개의 점들로 이루어진 집합으로서 $S$의 어느 세 점도 일직선 상에 있지 않고, 어떤 네 점도 한 원 상에 있지 않다. 어떤 원에 대해 $S$의 점 중 세 점이 원주 상에 있고, $n-1$개의 점은 이 원의 내부에, $n-1$개의 점은 이 원의 외부에 있을 때, 이 원을 ‘좋은’ 원이라 부르자. 좋은 원들의 개수를 $m$이라 하자. $m-n$이 항상 짝수임을 보여라.

2004 아시아태평양수학올림피아드 3번문제

평면 위에, 어느 세 점도 동일 직선 위에 있지 않은 2004개의 점으로 이루어진 집합 $S$를 생각하자. 이 집합 $S$의 서로 다른 두 점을 지나는 모든 직선의 집합을 $\mathcal L$이라 하자. 다음 조건을 만족시키도록 두 가지 이하의 색 만으로 $S$의 각 점을 칠할 수 있음을 증명하시오.

조건: $S$의 임의의 두 점 $p$, $q$에 대하여 $p$와 $q$ 사이를 가르는 $\mathcal L$의 직선들의 개수가 홀수일 필요충분조건은 $p$와 $q$가 같은 색인 것이다.

여기서 직선 $\ell$이 두 점 $p$, $q$를 가른다 함은 두 점 $p$, $q$의 어느 한 점도 $\ell$ 위에 있지 않고, $\ell$에 대하여 서로 반대쪽에 있다는 뜻이다.

2016 국제수학올림피아드 6번문제

평면에 $n\ge 2$개의 선분이 있다. 이 중 임의의 두 선분이 내부에서 교차하고, 어떤 세 선분도 한 점에서 만나지 않는다. 진용이는 각각의 선분마다 한 끝점을 선택해서 그 점에 개구리 한 마리를 놓되, 그 개구리가 그 선분의 다른 끝점을 향하도록 놓는다. 그리고 나서 손뼉을 $n-1$번 친다. 진용이가 손뼉을 한 번 칠 때마다, 모든 개구리는 앞으로 뛰어서 그 선분의 바로 다음 교점으로 이동한다. 개구리는 뛰는 방향을 절대로 바꾸지 않는다. 진용이는 개구리들이 뛰어 이동할 때, 어떤 두 개구리가 같은 교점에 동시에 있는 일이 발생하지 않도록 개구리를 배치하고자 한다.

(a) $n$이 홀수이면, 진용이가 원하는 대로 할 수 있음을 보여라.

(b) $n$이 짝수이면, 진용이가 원하는 대로 절대로 할 수 없음을 보여라.

2016 루마니아 수학 마스터 6번문제

3차원 유클리드 공간에 어느 4점도 한 평면 위에 있지 않는 $n$개 점의 집합이 있다. 이 집합은 두 부분집합 $\mathcal A$와 $\mathcal B$로 분할되어 있다. $\mathcal A$에 속한 점과 $\mathcal B$에 속한 점을 잇는 선분을 $n-1$개를 잘 모아서 다각형이 만들어지지 않게 하면 이 모임을 $\mathcal{AB}$-나무라 하자. 하나의 $\mathcal{AB}$-나무에서 다른 $\mathcal{AB}$나무를 아래와 같은 방식으로 얻는 연산이 있다고 하자: 만일 $\mathcal{AB}$-나무 안에 있는 서로 다른 세 선분 $A_1B_1$, $B_1A_2$, $A_2B_2$ (단, $A_1\in \mathcal A$)가 부등식 $A_1B_1+A_2B_2\gt A_1B_2+A_2B_1$을 만족시킬 때, 선분 $A_1B_1$을 지우고 대신 $A_1B_2$를 추가할 수 있다.
임의의 $\mathcal{AB}$-나무에서 시작하여 어떻게 위 연산을 적용하더라도 언젠가는 더 이상 위 연산을 적용할 수 없는 상황이 생긴다는 것을 증명하라.