Posts Tagged ‘ 그래프 ’

2010 KMO #4

4. 총 n명(n \geq 4)의 외교관들이 모여 있다. 임의의 네 외교관 A,B,C,D에 대하여, AB가 악수를 했고 BC가 악수를 했으며 CD가 악수를 했다면, 세 쌍 AC, AD, BD 중 악수를 했던 쌍이 반드시 존재한다. 이 때 다음을 증명하여라.
(a) 전체 외교관을 다음 성질이 만족하도록 공집합이 아닌 두 집합 X,Y로 나눌 수 있다. X에 속한 모든 외교관이 Y에 속한 어떤 외교관과도 악수를 하지 않았거나, X에 속한 모든 외교관이 Y에 속한 모든 외교관과 악수를 하였다.
(b) 어떤 두 외교관 A,B가 있어서 A,B 이외의 외교관 중에 A와 악수한 사람들의 모임과 B와 악수한 사람들의 모임이 같다.

약간 까다롭지만 어떻게 되긴 되네..

먼저 편의상 두 무리가 서로 악수를 안 했으면 적대관계, 전부 악수를 했으면 우호관계라 하자.

(a) 수학적 귀납법으로 보인다. 먼저 사람이 세 명 이하면 거의 트리비알.. 케바케. 네 명인 경우 선이 두 개 이하면 not connected이기 때문에 한 component vs 나머지로 만들면 적대관계로 만들 수 있음. 선이 세 개라면 가능한 경우는 삼각형이거나 한 명에게 세 명이 연결된 경우. 삼각형은 삼각형 vs 나머지 한 점으로 놓으면 적대관계이고, 후자의 경우 중심 한 명 vs 나머지 세 명으로 놓으면 우호관계가 된다. 선이 네 개 이상이라면 차수가 3 이상인 점이 존재하게 되어 그 점 vs 나머지 세 점으로 하면 우호관계가 되는데 예외가 딱 하나. 4-cycle. 그런데 이 경우 1-2-3-4-1이라면 1,3 vs 2,4가 우호관계.

이제 n명일 때 성립함을 가정한다. 그리고 n+1명일 때를 본다. 한 점 아무거나 택하고 그걸 제외한 것들을 보면 귀납법 가정에 의해 둘로 나눠 서로 연결되거나 서로 연결되지 않게 할 수 있다. 이 한 점을 x라 하고 이 두 집합을 A,B라 하자. 만약 A,B가 적대관계라면 이 그래프에서 선이 있는 것을 없애고 선이 없었던 곳엔 선을 만든다. 그래도 문제의 조건이 그대로 성립한다! (왜냐면 문제의 조건이 의미하는건 어떤 네 점을 택했을 때 A-B-C-D이고 B-/D-/-A-/-C가 된다는 건데, 위의 시행을 해도 똑같은 상황이 되기 때문이다.) 따라서 A,B가 우호관계일 때만 체크하면 된다. (편의상 x-/-yx,y 사이에 선이 없음을 뜻하기로.)

이제 a \in A, b \in B가 있어 a-x-/-b이거나 a-/-x-b가 성립함을 보이자. 만약 그렇지 않다면 A vs \{ x \}B vs \{ x \}가 전부 우호관계이거나 전부 적대관계이다. 어떤 경우든 A \cup \{ x \} vs B로 하면 해결됨. 이제 일반성을 잃지 않고 a -/- x-b라 하자.

B에서 x와 연결된 것들의 집합을 B_1, 나머지를 B_2라 하자. 앞에서 얻은 결과는 B_1이 공집합이 아니라는 것이다. 그러면 임의의 b_1 \in B_1, b_2 \in B_2에 대해 x-b_1-a-b_2인데 x-/-a,x-/-b_2이므로 b_1-b_2여야 한다. 따라서 B_1,B_2는 우호관계. 그러면 A \cup B_2 \cup \{ x \} vs B_1로 하면 된다.

따라서 수학적 귀납법으로 된다.

(b) 조금 서술이 까다로운데.. 디테일은 생략하기로 한다.

주요 키 포인트는, 주어진 조건을 만족하는 그래프에서 subgraph, 즉 점 집합의 부분집합을 잡고 원래 변 집합에서 이 점의 부분집합에 점을 갖는 것만 남긴 그래프를 보면 이것도 원래 조건을 만족한다는 것이다. (원래 조건 자체가 임의의 4-subgraph에 대해서 보는 intrinsic (?)한 조건이었기 때문에..) 그러면 (a)에 의해 우호나 적대 관계의 AB로 나눌 수 있다. 이를 A-B로 쓰자. 그러면 A,B 각각이 또 조건을 만족시키기 때문에 AA_1-A_2로, BB_1-B_2로 나눌 수 있다. 이를 (A_1-A_2)-(B_1-B_2)로 쓴다. 또 B_1을 두 개로 나누어 B_{11},B_{12}로 나누면 (A_1-A_2)-((B_{11}-B_{12})-B_2)로 쓰고, … 계속 하면 등장하는 모든 집합이 원소가 1개인 것들로 바꿀 수 있다. 이 과정에서 마지막 과정에 주목한다. 마지막에는 어떤 집합 XX_1-X_2로 나눴을텐데, 지금까지 오면서 X_1,X_2는 둘 다 X에 속하면서 다른 집합들과의 연결상태가 전부 동일했다. 따라서 X_1,X_2는 자신들끼리를 제외하면 다른 것들과의 연결상태가 동일하게 됨. 끝.

아마 원래 문제를 내고픈건 (b)였을텐데, (b) 하나만 내면 문제가 너무 어려워지니 그 과정인 (a)를 추가한 것이 아닐지?

Advertisements