티스토리 뷰

수학/이산수학

2N개의 점들

leejseo 2018. 1. 1. 21:57

문제. 평면 상에 어느 세 점도 일직선 상에 있지 않은 $2N$개의 점들이 있다. 이들 중 $N$개의 점은 빨간색, 나머지 $N$개의 점은 파란색으로 칠해져 있다고 한다. 빨간 점과 파란 점을 하나씩 짝지어 총 $N$개의 선분을 그으려 한다. 이 때, $N$개의 선분들이 서로 교차하지 않도록 하는 것이 가능함을 보여라.


풀이를 진행하기에 앞서, 그림의 퀄리티에 대한 양해를 부탁드립니다.


풀이 1. $N$에 대해 귀납법을 적용하자. $N=1$인 경우, 명확하다. 

$N=n-1$인 경우 성립한다고 가정하자.

이제, $n$개의 빨간 점과 $n$개의 파란 점이 있다고 하자. 만약, 이들의 볼록껍질 상에 빨간 점과 파란 점이 모두 존재한다면, 인접한 빨간 점과 파란 점을 이어주면, 귀납 가설에 의해 증명이 종료된다. 이제, 일반성을 잃지 않고, 볼록껍질 상에 빨간 점만 존재한다고 가정하자. $2n$개의 점들 중 두 점을 택해 만들어지는 ${}_{2n} C_2$개의 직선들 가운데 그 어느 것과도 수직하지 않은 직선 $l$을 잡고, $l$ 상에 점들을 투영시켜서 생각하자. (편의상 $l$은 $x$축에 수직하지 않다고 하자.) 이제, 함수 $f: \mathbb{R} \to \mathbb{Z}$를 다음과 같이 정의하자: 

$f(t) = $($x$좌표가 $t$이하인 $l$에 투영된 점 들 가운데 빨간 점의 수)$-$($x$좌표가 $t$이하인 $l$에 투영된 점 들 가운데 파란 점의 수)

그러면, 아래 그림과 같이 $a$와 $c$를 잡아주면, $f(a) > 0$, $f(c) < 0$이고, $f$의 값은 한번에 $\pm 1$씩만 변화할 수 있으므로, $a$와 $c$ 사이의 어떤 점 $b$가 존재해 $f(b) = 0$이다. 그러면, $b$를 기준으로 $b$의 왼쪽($b$포함)과 오른쪽에 각각 귀납가설을 적용해주면, 증명이 종료된다.


풀이 2. 편의상 빨간 점들을 $A_1, A_2 , \cdots, A_N$, 파란 점들을 $B_1, B_2, \cdots , B_N$으로 표기하고, $S_N$을 길이가 $N$인 순열들의 모음으로 표기하자. 그러면, 각각의 빨간 점들과 파란 점들의 matching에 대응되는 $S_N$의 원소가 존재한다. 이제, $$\min \left \{ \sum_{i=1}^{N} \overline{A_i B}_{\sigma(i)} \mid \sigma \in S_N  \right \}$$의 길이를 가지는 matching이 존재하며, 이것을 택하자. 그러면, 삼각부등식에 의해 이것은 조건을 만족하는 matching이 된다. (보다 자세히 설명하자면, 아래 그림에서 검은 선분 2개의 길이의 합이 초록 선분 2개의 길이의 합보다 짧기 때문이다.) 따라서, 증명이 종료된다.


응용. KOI 2016 중등부 4번

'수학 > 이산수학' 카테고리의 다른 글

고정된 크기의 클릭의 수  (0) 2018.04.11
Projective Plane의 Blocking Set의 크기  (0) 2018.02.03
2N개의 점들  (0) 2018.01.01
그들 사이의 거리  (0) 2017.09.18
Erdős–Ko–Rado 정리  (0) 2017.07.29
간단한 poset을 이용하는 문제  (0) 2017.07.27
댓글
댓글쓰기 폼