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

평면 위의 직선들이 어느 두 직선도 서로 평행하지 않고, 어느 세 직선도 한 점에서 만나지 않을 때, 그 직선들이 ‘보편적으로 배치되어 있다’고 하자. 보편적으로 배치되어 있는 직선들은 평면을 여러개의 영역으로 쪼개고, 그 영역들 중 일부는 유한의 넓이를 갖는다. 이처럼 유한의 넓이를 갖는 영역을 그 배치의 ‘유한영역’이라고 할 때, 다음을 증명하여라: 충분히 큰 모든 $n$에 대하여, $n$개의 직선들로 이루어진 어떠한 보편적 배치에 대하여도, 최소한 $\sqrt{n}$개의 직선을 파란색으로 칠하되 그 배치의 어떠한 유한영역도 그 경계를 이루는 변들이 모두 파랗지는 않도록 칠할 수 있는 방법이 있다.

Note: 만일 $\sqrt n$에 대해서는 결과를 구하지는 못하였으나 대신 $c\sqrt n$에 대한 결과를 구한 경우에는, 상수 $c$의 값에 따라 부분점수를 준다.

GD Star Rating
loading...