Let's MATH PARTY !

즐거운 파티를 이루는 요소에는 맛있는 음식과 신나는 공연, 특별한 장소 등 많이 있지만 수학자들은 얼마나 많은 참석자들이 서로 아는 사이인지에 관심을 가졌다. 사실 참석자 모두가 서로를 안다면, 편안하고 즐거운 분위기에서 파티를 즐길 수 있다. 아는 사람이 아무도 없는 경우에도 서로를 알아가는 재미를 느낄 수 있다. 하지만 단 한 사람만 제외하고 나머지 사람들이 모두 아는 사이라면, 그 한 사람만 파티에서 소외될 가능성이 크다. 반대로 한 사람은 모든 사람들을 알지만, 나머지 사람들끼리 서로 모르는 경우라면 한 사람에게만 관심이 집중돼 자칫 파티가 지루할 수 있다.

따라서 파티를 계획할 때에는 서로 친구인 사람과 모르는 사람의 수를 균형 맞추는 것이 중요하다. 수학자들은 바로 이 문제를 연구했다. 일명 ‘파티 문제’다.

파티 문제를 풀기 위해선 먼저 몇 가지 가정을 해야 한다.





이제 서로 친구인 사람 3명이 반드시 있거나, 서로 전혀 모르는 사이인 사람 3명이 반드시 있으려면 최소 몇 명을 초대해야 하는지 구해 보자. 그런데 만약 3명을 2명으로 바꾸면 답은 아주 간단해진다. 어떤 두 사람을 초대해도 둘은 서로 친구이거나 모르는 사이기 때문이다.

하지만 3명이 되면 답은 쉽게 구해지지 않는다. 예를 들어 정치, 희열, 호동을 초대한다고 가정하자. 정치는 희열
과 친구고, 희열은 호동과 친구다. 그런데 호동은 정치를 모를 수 있다. 그렇다면 이 셋은 서로 친구라고 할 수 없다. 즉 3명을 초대하는 것으로는 부족하다.

이제 4명을 초대해 보자. 3명일 때처럼 안 되는 예 하나만을 찾으면 되지만, 사람수가 많아지면 바로 떠올리기가 쉽지 않다. 따라서 수학자들은 그래프 이론을 이용했다.



먼저 문제를 그래프 이론 문제로 바꿔 보자. 사람을 꼭짓점, 사람 사이의 관계를 선으로 표시한다. 이때 서로 친구 사이라면 빨간색, 전혀 모르는 사이라면 파란색으로 나타낸다. 그러면 문제는 ‘꼭짓점들 사이에 선을 어떻게 연결해도 파란색 또는 빨간색 삼각형이 반드시 존재하려면, 꼭짓점이 최소 몇 개 필요한가?’로 바뀐다.

(중략)