‘한 모임에서 서로 아는 3명(s), 또는 서로 모르는 3명(t)이 반드시 존재하려면 최소 몇 명이 모여야 할까?’ 모두가 편안하고 즐거운 완벽한 파티를 열기 위해 꼭 따져봐야 할 것 같은 일명 ‘파티 문제'입니다. 파티 문제의 본래 이름은 ‘램지 수 문제'입니다. s와 t의 값이 작을 땐 구하기 쉽지만, 값이 커지면 따져야 할 경우의 수가 많아 수학자들도
거의 100년 동안 계속해서 답을 구하는 중입니다. 그런데 최근 수학계가 흥분할 만한 램지 수 연구가 발표됐습니다.

영국의 철학자 프랭크 램지는 1928년 ‘사람이 충분히 많다면 그중 서로 모두 아는 관계인 s명 혹은 서로 전혀 모르는 관계인 t명이 반드시 있다’는 ‘램지 정리’를 발표했습니다. 위의 문제는 1947년 헝가리 수학자 팔 에르되시와 죄르지 세케레시가 이를 만족하는 최소 정수 N을 ‘램지 수’라 부르며 R(s,t)=N으로 정의해 널리 알려졌으며, ‘램지 수 문제’ 또는 ‘파티 문제’라고 불립니다.

램지 수 문제는 무엇인가

램지 수 문제의 이해를 돕기 위해 쉬운 경우들을 생각해 보겠습니다. 우선 R(s,t)=R(t,s)가 됩니다. 서로 아는 관계와 서로 모르는 경우를 정반대로 생각하면 되니까요. 그리고 R(2,t)=t 가 되는 건 조금만 생각해 보면 당연합니다. 파티 구성원 중 서로 아는 사람 2명이 안 되게 하려면, 무조건 서로 몰라야 합니다. 즉, 서로 모두 모르는 사람 t명일 최소 인원은 t명인 거죠(직접 그리며 확인해보면 금방 알 수 있습니다).

그럼 서로 모두 아는 사람 3명, 또는 서로 모두 모르는 사람 3명이 있으려면 최소 몇 명이 모여야 할까요? 확인하는 방법은 간단합니다. 파티 구성원이 4명일 때, 5명일 때, 6명일 때 7명일 때, n명일 때까지. 서로 모두 아는 사람 3명 또는 서로 모두 모르는 사람 3명이 절대 나타나지 않도록 점과 선으로 그려보는 겁니다. 그러다 보면 서로 모두 아는 사람 3명 또는 서로 모두 모르는 사람 3명이 나타날 수밖에 없는 인원수를 발견할 수 있을 겁니다.

자, 직접 그려서 확인해 봅시다. 과학동아 6명의 기자들로 서로 아는 사람은 파란색, 서로 모르는 사람은 빨간색으로 표시합니다. 먼저 창욱이 미래, 태희, 소연 이렇게 3명과 서로 안다고 가정해 보죠. 이후 ‘창욱-미래-태희’가 서로 알게 되면 증명이 너무 쉬워지니, ‘미래-태희’를 서로 모르는 사이이라 둡시다. ‘태희-소연’, ‘미래-소연’도 마찬가지입니다. 아차, 이렇게 하니 결국 ‘미래-태희-소연’이 서로 모르는 세 사람이 돼버렸군요. 그렇다고 ‘미래-소연’을 다시 아는 사람으로 정리하자니, ‘창욱-미래-소연’이 아는 사이가 됩니다. 한편 창욱과 서로 아는 사람이 2명 이하일 때는, 창욱과 서로 모르는 사람 3명을 뽑을 수 있으니 비슷한 방법으로 같은 결론을 내릴 수 있습니다. 서로 아는 관계와 서로 모르는 경우를 정반대로 생각해도 되고요. 맞습니다. 6명일 땐, 서로서로 모두 아는 3명 또는 서로서로 모두 모르는 3명이 무조건 생길 수밖에 없는 거죠. 5명이 있으면 그런 3명을 찾을 수 없는 경우가 생길까요? 네, 생깁니다. 그런 경우는 직접 찾아보시길 추천드립니다.

일반적으로 생각해 볼 수 있는 문제는 t일 때 R(3,t), R(4,tt,t)의 값들을 찾는 것입니다. 연구자들은 제일 처음에 있는 R(3,t)와 마지막에 있는 R(t,t)를 구하는 데 많이 도전했습니다. 많은 수학자들의 도전 끝에 밝혀진 램지 수는 다음 페이지에서 확인할 수 있습니다.

컴퓨터로 구할 순 없을까?

위 표를 보면 알 수 있지만, 꽤 낮은 숫자인 R(5,5)의 값과 R(4,6)의 값도 아직 모르는 상태입니다. R(4,5)는 1995년 스타니스와프 라지조프스키 미국 로체스터공대 컴퓨터공학과 교수와 브렌든 맥케이 호주국립대 컴퓨터공학과 교수가 수년간의 컴퓨터 계산을 통해 그 값이 25임을 알아냈습니다. 수년이 걸린 이유는 컴퓨터가 하나씩 따져 계산해야 하는 양이 매우 많기 때문입니다.

지금은 컴퓨터 계산 능력이 훨씬 발전됐으니 다른 문제도 풀 수 있지 않을까요? 그 답을 하기 위해선 작은 램지 수를 알아내기 위해 계산이 얼마나 필요한지 확인해봐야 합니다. R(4,5)=25을 컴퓨터로 증명하기 위해 점검해야할 경우의 수를 알아봅시다. 25명의 사람들 중에 2명을 묶는 가짓수가 (25×이고 그렇게 묶은 2명이 서로 아는 경우와 서로 모르는 경우 2가지가 있으니 총 경우의 수는 2³⁰⁰입니다. 계산하면 약 2.037×10⁹⁰이죠. 이 경우들을 꼭 다 생각해야 하는 것은 아닙니다. 다른 경우지만 구조가 정확히 같은 경우를 뜻하는 동형(isomorphism)의 경우에는 같은 구조를 갖는 경우 중 하나만 대표로 생각하면 됩니다. 같은 구조인 경우의 수의 최댓값은 25!이니 최소 2³⁰⁰은 따져봐야 합니다. 이는 약 1.313×10⁶⁵ 정도 됩니다.

아직 밝혀지지 않은 R(4,6)의 하한은 36입니다(하한은 구하려는 값의 낮은 쪽 경곗값을 뜻합니다). 아까의 방식대로 계산하면 1.197×10¹⁴⁸로, 149자릿수의 경우의 수를 점검해야 합니다. 따라서, 컴퓨팅 기술이 발전해서 하한이 36인 R(4,6)까지(경우의 수가 적어도 149자리수)는 가능할지 몰라도, R(5,5)의 값(경우의 수가 적어도 220자리수)을 찾아내기는 상당히 힘들 거라고 예상할 수 있습니다.

크기 함수로 답을 찾은 R(3,t)

앞서 설명한 것처럼 하한은 구하려는 값의 낮은 쪽 경곗값을 뜻하고, 상한은 높은 쪽 경곗값을 뜻합니다. 일반적으로, 위 부등식과 같이 상한과 하한의 차이가 상수뿐일 때 크기정도를 찾았다고 합니다. 영어로는 ‘order of magnitude’라하는데 보통 ‘크기 정도’ 또는 ‘계산 차수’라 불리고 있습니다. 조합론 분야에서 오래 전부터 크기 정도를 사용해 왔고 컴퓨터가 발전한 후로는 알고리즘들이 얼마나 효율적인지를 나타내는 지표를 표시할 때 크기 정도를 많이 사용하면서 계산 차수라는 이름으로도 쓰이고 있습니다. 두 표현 모두 알고리즘에 특화돼 쓰이는 경우도 있어, 이 글에서만은 ‘크기 함수’라는 이름을 사용하는 것이 좋을 것 같습니다.

R(3,t)의 크기 함수를 밝히는 문제는 앞서 소개한 팔 에르되시가 250달러의 상금을 제시한 문제였습니다. 에르되시는 수학 문제의 난이도에 따라 적게는 1달러부터 많게는 수천 달러까지 상금을 매겼고 지금도 그 문제를 풀면 상금이 지급됩니다. 사람들이 이 문제에 상금이 있었다는 사실을 잘 모르고 있었는지 최근에서야 250달러짜리 수표를 필자가 수령하게 됐습니다.

30년 만에 한 걸음 더, 근삿값을 찾은 R(4,t)

R(3,t)의 크기 함수가 밝혀진 지 30년 가까이 지난 2023년 7월 6일 R(4,t)의 크기 함수에 대한 괄목할 만한 연구 성과가 나왔습니다. ^{doi: 10.48550/arXiv.2306.04007} 샘 매튜 벨기에 브뤼셀대 박사후연구원과 자크 베르스트라에테 미국 UC샌디에이고 수학과 교수가 획기적으로 가까운 R(4,t)의 하한을 찾은 겁니다.

이 성과는 약 10개월의 검증을 거쳐 수학계 최고의 권위 있는 학술지 중 하나인 ‘Annals of Mathematics’에 게재될 예정입니다. 여기에 실리는 연구들은 주로 수학계의 발전에 큰 영향을 미친 내용들입니다. 때문에 수학자들은 자신의 연구가 해당 학술지에 게재되는 것을 굉장한 영광으로 여기죠.

이번 연구 성과는 R(4,t)의 크기 함수를 완전히 찾은 것은 아니지만, R(4,t)의 하한이 획기적으로 상한과 가까워진 연구 결과입니다. 수학자들은 하한과 상한이 거의 비슷한 값이 되도록 조금씩 추려 나가며 문제의 실마리를 풀곤 합니다. 이 문제 역시 R(4,t)의 크기 함수를 상한과 하한의 간극을 좁히며 풀어내려는 거죠. R(4,t)의 상한은 다른 연구자의 성과로 먼저 알려져 있었고, 이번에 매튜 박사와 베르스트라에테 교수가

위와 같은 R(4,t)의 하한에 대한 증명에도 에르되시가 250달러의 상금을 제시했습니다. 이 상금은 벌써 지급했거나 빠른 시실 안에 지급할 예정인 것으로 알고 있습니다. 지금 생각해 보면 뒤늦게 제게 상금이 온 것이 매튜 박사와 베르스트라에테 교수에게 250달러의 상금을 지급하려는 과정에서 제가 해결한 R(3,t)의 크기 함수 문제에도 상금이 있다는 것을 뒤늦게 인지하게 된 것 같습니다. 제가 R(4,t)에 대한 좋은 결과를 도출해 내지 못해 아쉽지만, 한 가지 위안이 되는 것은 단독으로 논문을 발표한 저는 250달러를 다 받게 됐는데 그들은 둘이 나누게 될 것 같다는 사실입니다(농담입니다).

수학은 왜 이런 연구를 하는 걸까?

이렇게 수학계를 들썩이게 한 새로운 램지 수 연구 결과를 소개해봤습니다. 자, 이쯤 되면 드는 생각이 있을 겁니다. 수학자들은 왜 이런 증명에 수 년, 수십 년을 매달리는 걸까요?

세 사람이 있으면

그 중 두 사람은 같은 성별(gender)이다.

- 다니엘 클라이트만

미국의 수학자 다니엘 클라이트만이 한 말인데 너무 당연한 말이죠? 이 단순한 말은 n명의 사람이 입은 옷 색이 n-1가지이면 같은 색 옷을 입은 사람이 2명 (또는 그 이상) 있다는 내용의 ‘비둘기집 원리’로 일반화할 수 있습니다. 이 원리를 좀 더 확장하면 램지 수 문제가 됩니다. 비둘기집 원리 설명에서 남자, 여자 또는 옷 색깔 등을 두 사람이 서로 아는 관계와 서로 모르는 관계(한쪽만 아는 관계도 포함함)로 바꾸면 되죠. 이처럼 수학은 작은 구조에 해당하는 논리가 좀 더 큰 구조나 더 일반적인 구조에서도 작용하는지를 연구합니다.

여러 종목이 있는 스포츠에서도 한 종목의 경기 방법 등을 이해하면 다른 종목의 경기 방법도 이해하기 쉬워지는데요. 아마 공통된 원리가 있기 때문일 것입니다. 그리고 여러 스포츠를 잘 관찰하다 보면 모든 스포츠에서 공통으로 적용되는 원리가 있다는 것을 알 수 있게 됩니다. 한쪽에만 유리할 수 있는 방법을 배제하고 최대한 공평하게 경기를 진행해야 해야 한다는 원리죠.

여러 스포츠의 규칙을 관찰하다 보면 원리를 찾을 수 있는 것처럼, 수학에서도 어떤 체계 안에 있는 많은 구조에 보편타당하게 적용할 수 있는 원리를 찾는 과정의 시작은 관찰입니다. 다만, 수학에서는 엄밀하고 정확하게 원리를 표현하고 증명해야 합니다. 진위를 분명히 판단할 수 있는 명제만을 다루는 것도 수학만의 다른 점입니다.

예를 들어 ‘오늘 날씨가 추운지 더운지’는 사람마다 판단의 기준이 다르기 때문에 명제가 아닙니다. 오늘 서울 날씨가 영하로 내려가는 때가 있는지 아닌지와 같이 분명히 판단할 수 있는 명제만을 생각합니다. 물론 기상청에서 정한 기준대로 정확하게 온도를 측정하고 있다는 가정하에서 얘기하고 있다는 전제 조건도 잊는 일이 없어야 합니다. 명제가 아니라면 그 진위를 정확히 판단하는 기준이 없어 보편타당하게 적용할 수 있는 원리인지 알 수 없으므로 수학에서는 할 일이 많지 않습니다.

수학이 왜 이런 연구를 하는지 설명하기 위해 수학이 어떤 학문인지 설명하다 보니 말이 길었습니다. 다시 정리하면 어떤 구조들 속에 보편타당성이 있는 원리가 있는지 알아보고, 있다면 그 원리를 이해하는 것이 수학의 기본자세입니다. 램지 수 문제도 마찬가지입니다. ‘한 모임에서 서로 아는 s명, 또는 서로 모르는 t명이 반드시 존재하려면 최소 몇 명이 모여야 할까?’라는 문제를 풀면서, 그 속에 어떤 원리가 있는지, t가 늘어날수록 왜 계산이 복잡해지는지, 복잡해진다면 어떤 형태로 또는 얼마나 복잡해지는지, 뭐가 됐든 그 원리를 이해하기 위한 모든 노력을 기울이죠. 사람들이 살아가면서 가치관이 생기고 어떤 일에 달인이 되는 것도 이와 비슷한 과정을 거친다고 할 수 있겠습니다.

이런 작업을 통해 원리를 찾는 것은 물론, 원리를 찾는 여러 가지 방법을 모아 ‘원리 찾는 원리’를 알아내려고 하는 학문이 수학입니다. 그러니 수학자들이 ‘이런’ 연구를 하는 건 어찌 보면 당연한 일인 셈이죠.

❋필자소개

김정한. 한국의 수학자로, 연세대에서 물리학과 수리물리를 전공하고 미국 럿거스대에서 수학으로 박사학위를 취득했다. 카네기멜론대, 벨 연구소, 마이크로소프트 리서치를 거쳐 연세대 수학과 교수로 임용된 후, 2013년부터는 고등과학원 계산과학부 교수로 재직 중이다.
연구 분야는 조합론과 계산수학이며, 램지의 정리에서 R(3,t) 값의 크기 함수를 구해 1997년 풀커슨 상을 수상했다.