수학적으로 가장 완벽한 파티는?

크리스마스나 결혼처럼 특별한 날에만 열던 파티가 최근에는 각자 음식을 준비해 와서 나눠 먹는 포틀럭 파티, 파자마 파티, 댄스 파티 등으로 다양해지며 언제나 즐길 수 있게 됐다. 

이색 파티를 즐기는 파티족들은 파티 플래너를 고용해 파티 장소부터 조명, 프로그램 구성까지 세심하게 신경을 쓰기도 한다. 하지만 파티 플래너도 해결할 수 없는 문제가 있다. 바로 파티에 참석하는 구성원들의 관계다. 

사실 참석자 모두가 서로 친구사이라면 편안하고 즐거운 분위기에서 파티를 즐길 수 있다. 아는 사람이 없어도 서로를 알아가는 재미를 느낄 수 있다. 

그러나 단 한 사람만 제외하고 나머지 사람들이 모두 아는 사이라면, 그는 파티에서 소외될 가능성이 크다. 반대로 한 사람은 모든 사람들을 알지만, 나머지 사람들은 서로 모르는 경우라면 그에게만 관심이 집중돼 자칫 파티가 지루해 질 수 있다.

파티를 계획할 때는 서로 아는 사람과 모르는 사람의 수를 균형 맞추는 게 중요하다. 수학자들은 서로 친구인 사람이 k명이 반드시 있거나, 서로 전혀 모르는 사이인 사람 l명이 반드시 있으려면 최소 몇 명을 초대해야 하는지 구하는 문제를 연구했다. 일명 ‘파티 문제’다.

서로 친구인 사람을 빨간선으로, 서로 모르는 사람을 파란선으로 연결할 때 최소 6명을 초대하면 언제나 빨간색 또는 파란색 삼각형이 그려진다. 서로 친구거나 모르는 사람이 3명씩 반드시 존재한다. 수학동아 제공

 수학자들은 그래프 이론을 이용해 이 문제를 해결했다. 그래프 이론이란, 꼭짓점과 두 꼭짓점을 연결하는 선으로 이뤄진 그림인 그래프를 이용해 수학 문제를 해결하는 이론이다. 사람을 꼭짓점으로, 두 사람 사이의 관계를 색깔 있는 선으로 나타내면 파티 문제를 그래프로 표현할 수 있다.

그 결과 서로 친구인 사람과 모르는 사람이 각각 3명일 때는 6명, 각각 4명일 때는 18명이라는 사실을 알아냈다. 하지만 5명만 돼도 따져야 하는 경우의 수가 2¹¹⁷⁶이나 된다. 10명이라면 수백억 가지나 돼 속도가 아주 빠른 슈퍼컴퓨터로도 구할 수 없다. 

수학자들은 답이 될 수 있는 수의 범위를 구하는 공식을 개발했다. 정확한 답을 구할 수 없지만 상한과 하한을 구해, 따져야 하는 경우의 수를 줄이기 위해서다. 이 방법을 사용해보니, 어떤 파티에서 서로 친구인 사람 5명 또는 서로 전혀 모르는 사람 5명이 반드시 존재하려면 최소 43명에서 49명 사이를 초대해야 한다는 것을 밝혀냈다.

1930년에는 영국의 수학자 프랭크 램지가 모든 파티 문제를 다룰 수 있는 획기적인 연구 결과를 발표했다. 바로 램지 정리다. 램지 정리란 꼭짓점의 크기가 충분히 큰 완전그래프의 선을 색칠할 때 동일한 색의 선으로만 구성된 완전그래프가 항상 포함돼 있다는 이론이다. 이를 통해 서로 친구이거나 서로 모르는 사람이 반드시 존재하도록 파티를 구성할 수 있다는 것이 증명됐다.

사실 수학자들은 램지 정리 발표 이전까지 파티 문제의 답이 항상 존재하는지 의문을 품고 있었다. 사람의 수를 조금만 늘려도 따져야 할 경우가 너무 많아 계산할 엄두가 나지 않았기 때문이다. 하지만 램지 정리로 모든 고민이 말끔히 해결됐다.

램지정리. - (주)동아사이언스 제공

한편 1997년에는 연세대 수학과 김정한 교수가 서로 친구인 사람이 3명이고, 모르는 사람이 n명일 때 파티 문제에서 초대해야 할 사람의 수 범위를 구하는 공식을 발견해 아시아인 최초로 풀커슨상을 수상하는 쾌거를 이뤘다. 풀커슨상이란 미국수학회와 수학적 프로그래밍 학회에서 3년에 한 번 주는 것으로, 이산수학(離散數學) 분야에서 가장 뛰어난 논문을 쓴 사람에게 주는 상이다.

수학자들은 파티 문제의 답 중 최소 정수를 램지수라고 정의하고, 램지수를 구하기 위한 노력을 계속하고 있다. 램지수는 파티 문제에서 시작했지만 무질서한 것에서 질서를 찾아낼 수 있어, 네트워크와 인공지능 등 다양한 분야에서 활용되기 때문이다.

수학동아