완전한 무질서는 없다

여섯 명이 모이면 서로 아는 세 사람이나 서로 모르는 세 사람이 반드시 있다. 충분히 크면 어디에나 질서가 숨어 있다는 이론과, 그것을 동전 던지기로 증명한 에르되시.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속의 선과 칸은 눌러서 색을 바꾸고, 점은 끌어서 옮길 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

파티에 여섯 명이 모였습니다. 그중 어떤 두 사람은 원래 아는 사이이고, 어떤 두 사람은 오늘 처음 봅니다. 누가 누구를 아는지는 전혀 모릅니다. 그런데도 다음과 같이 장담할 수 있습니다. 이 여섯 명 가운데에는 서로 다 아는 세 사람이 있거나, 서로 다 모르는 세 사람이 있다. 손님이 다섯 명이면 이 장담은 틀릴 수 있습니다.

이 문제는 1947년 헝가리의 고등학생 수학 경시대회에 나왔습니다. 헝가리에서는 1894년부터 고등학교를 갓 마친 학생들의 전국 경시대회가 열렸는데, 이 대회는 같은 해 창간된 고등학생 수학 잡지와 함께 부다페스트의 수학자들을 길러 낸 토양이 되었습니다. 같은 문제가 1953년에는 미국의 대학생 경시대회인 퍼트넘 경시대회에도 나왔습니다. 풀이는 몇 줄이면 끝납니다. 하지만 이 작은 퍼즐 뒤에는 20세기 수학의 한 갈래가 통째로 있습니다. 아무렇게나 섞어 놓아도 대상이 충분히 크기만 하면 그 안 어딘가에 반드시 질서 잡힌 조각이 생긴다는 이론, 램지 이론⁠(Ramsey theory)⁠입니다.

이론의 이름은 케임브리지의 프랭크 램지에게서 왔습니다. 그는 1928년 논리학 문제를 풀다가 이 사실을 보조정리(큰 정리를 증명하는 도중에 필요해 먼저 증명해 두는 작은 정리)로 증명했고, 2년 뒤 스물여섯 살에 세상을 떠났습니다. 이 글은 여섯 명의 파티에서 출발해, 수를 색칠하는 정리들과 부다페스트 공원의 수학 모임을 거쳐, 동전 던지기로 존재를 증명한 에르되시, 소수⁠(prime number)⁠ 속에 숨은 등차수열⁠(arithmetic progression)⁠, 그리고 우연 속에서 무늬를 읽어 내는 사람의 눈까지 따라갑니다.

1 · 한 색 삼각형여섯 명의 파티

이 절의 물음은 이것입니다. 머리말의 장담은 정말 맞을까? 그리고 왜 다섯 명으로는 안 되고 여섯 명이어야 할까? 먼저 문제를 그림으로 옮기고, 직접 칠해 보며 확인합니다.

사람을 점으로, 두 사람의 관계를 두 점을 잇는 선으로 그려 봅시다. 점과 선으로 된 이런 그림을 그래프라고 부릅니다. 여기서는 모든 두 사람 사이에 관계가 있으니(알거나 모르거나) 모든 두 점이 이어져 있습니다. 이런 그래프를 점이 $n$개인 완전 그래프라 하고 $K_n$으로 적습니다. 선은 두 점을 고르는 방법의 수만큼, 곧 $n(n-1)/2$개 있습니다. 점마다 다른 $n-1$개의 점으로 선이 나가니 $n(n-1)$이 되는데, 선 하나를 양 끝에서 두 번 센 셈이라 2로 나눕니다. 다섯 명이면 5 × 4 ÷ 2 = 10개, 여섯 명이면 6 × 5 ÷ 2 = 15개입니다.

이제 서로 아는 사이는 빨강, 모르는 사이는 파랑으로 선을 칠합니다. "서로 다 아는 세 사람"은 세 변이 모두 빨강인 삼각형, "서로 다 모르는 세 사람"은 모두 파랑인 삼각형입니다. 질문은 이렇게 바뀝니다. 한 색으로만 된 삼각형이 생기지 않게 모든 선을 칠할 수 있을까? 손님 수를 으로 골라 직접 해 보세요. 선을 누를 때마다 빨강, 파랑, 빈칸 차례로 바뀝니다. 목표는 모든 선을 칠하고도 노랗게 빛나는 삼각형이 하나도 없게 하는 것입니다.

무작위로 칠하기 지우기 오각형 칠하기 ▶ 모든 경우 훑기

다섯 명과 여섯 명 사이에 선이 그어졌습니다. 여섯 명의 파티에서는 한 색 삼각형을 피할 수 없고, 다섯 명이면 피할 수 있습니다. 이 사실을 놀이로 만든 사람도 있습니다. 1969년 암호학자 구스타부스 시먼스가 소개한 '심'이라는 게임에서는 두 사람이 번갈아 여섯 점 사이의 선을 자기 색으로 칠하고, 자기 색 삼각형을 먼저 만드는 쪽이 집니다. 위 그림의 방식()을 눌러 ‘심 게임’으로 바꾸면 컴퓨터와 둘 수 있습니다. 여섯 명의 파티 정리 때문에 이 게임은 절대 비기지 않습니다. 15개의 선이 다 칠해지기 전에 누군가는 반드시 삼각형을 만듭니다. 1974년 컴퓨터 탐색으로, 둘 다 최선을 다하면 나중에 두는 쪽이 이긴다는 것이 밝혀졌습니다.

나중에 두는 쪽이 이긴다는 결과는 다른 게임과 견주어 보면 눈길을 끕니다. 헥스는 육각형 칸으로 된 마름모꼴 판에 두 사람이 번갈아 자기 색 돌을 놓아, 자기에게 정해진 맞은편 두 변을 먼저 잇는 쪽이 이기는 게임입니다. 헥스도 비기는 일이 없는데, 여기서는 먼저 두는 쪽이 이긴다는 것을 '전략 훔치기⁠(strategy stealing)⁠'로 증명할 수 있습니다. 나중 두는 쪽에게 반드시 이기는 전략⁠(winning strategy)⁠이 있다고 해 봅시다. 그러면 먼저 두는 쪽이 아무 데나 한 수 둔 뒤 그 전략을 흉내 내어 이길 수 있으니 모순입니다. 이 논증의 자세한 모습은 「이기는 쪽이 존재한다」 1절에 있습니다. 그러나 심에서는 이 논증이 통하지 않습니다. 헥스에서는 판에 내 돌이 하나 더 있는 것이 결코 손해가 아니지만, 심에서는 선을 하나 더 칠해 두는 것이 오히려 삼각형을 떠안는 짐이 될 수 있기 때문입니다.

모든 경우를 훑는 방법은 여섯 명까지만 통합니다. 여섯 명의 선 15개를 저마다 두 색 가운데 하나로 칠하니 색칠은 $2^{15} = 32{,}768$가지(2를 15번 곱한 수)입니다. 사람이 43명이면 선이 43 × 42 ÷ 2 = 903개이고, 색칠하는 방법은 $2^{903}$가지로 우주의 원자 수보다 훨씬 많습니다. 여섯 명에서 성공이 보장되는 이유를 찾아야 합니다. 정리하면, 다섯 명은 한 색 삼각형을 피할 수 있고(오각형 칠하기), 여섯 명은 피할 수 없다는 것을 컴퓨터로 확인했지만, 아직 그 까닭은 모릅니다.

2 · 비둘기집왜 여섯이면 충분한가

이 절의 물음은 이것입니다. 여섯 명이면 왜 반드시 한 색 삼각형이 생길까? 그리고 같은 이유가 더 큰 무리에 대해서는 무엇을 알려 줄까?

이유는 비둘기에서 나옵니다. 비둘기 다섯 마리가 둥지 두 개에 들어가면 어느 한 둥지에는 적어도 세 마리가 있습니다. 둘씩만 들어가면 넷밖에 못 들어가니까요. 너무 당연해 보이는 이 원리를 비둘기집 원리⁠(pigeonhole principle)⁠라고 부릅니다. 조합론⁠(combinatorics)⁠, 곧 유한한 대상들을 세고 늘어놓는 수학에서 가장 자주 쓰이는 도구입니다.

여섯 명 가운데 한 사람 A를 봅시다. A에서 다른 다섯 명에게 가는 선 다섯 개가 비둘기이고, 빨강과 파랑이 두 상자입니다. 그러니 한 색의 선이 적어도 세 개입니다. 아래 그림에서 A의 선을 눌러 색을 바꿔 보세요. 어떻게 바꿔도 한 상자에는 셋 이상이 모입니다.

A의 색 모두 뒤집기

이제 셋 이상 모인 쪽이 빨강이라고 하고, 그 세 사람을 B, C, D라고 합시다. 이 셋 사이의 선 세 개를 보면 됩니다. 그중 하나라도 빨강이면 그 선의 두 끝과 A가 빨강 삼각형을 이룹니다. 하나도 빨강이 아니면 세 선이 모두 파랑이니, B, C, D 자신이 파랑 삼각형입니다. 어느 쪽이든 삼각형이 생깁니다. 점선을 눌러 빠져나갈 길을 찾아보세요. 없습니다.

이것이 증명의 전부입니다. 정리하면, A 한 사람의 선 다섯 개 가운데 한 색이 셋 이상이고(비둘기집), 그 세 사람 사이의 선 세 개가 어느 색이든 삼각형이 생깁니다. 다섯 명의 오각형은 다섯 명으로는 모자란다는 것을, 비둘기집은 여섯 명이면 충분하다는 것을 보여 줍니다. 이 경계를 이름으로 부르기로 합니다. 어떻게 두 색으로 칠해도 빨강 $K_s$(서로 다 이어진 $s$개의 점)나 파랑 $K_t$가 반드시 생기는 가장 작은 $n$을 램지 수⁠(Ramsey number)⁠ $R(s, t)$라고 합니다. 파티 문제의 답은 이렇게 적힙니다.

같은 논증은 더 큰 수에도 그대로 통합니다. 한 사람 A를 골라 A와 빨강으로 이어진 사람들(빨강 쪽 이웃)과 파랑으로 이어진 사람들(파랑 쪽 이웃)로 나눕니다. 빨강 쪽 이웃이 $R(s-1, t)$명 이상이면, 그 안에서 빨강 $K_{s-1}$이 나와 A와 함께 빨강 $K_s$가 되거나(A는 그들 모두와 빨강으로 이어져 있으니까요), 파랑 $K_t$가 나옵니다. 파랑 쪽 이웃이 $R(s, t-1)$명 이상일 때도 같습니다.

그러면 두 경우 가운데 하나가 반드시 일어나려면 사람이 몇 명이면 될까요? 모두 $R(s-1,t) + R(s,t-1)$명이라 해 봅시다. A의 이웃은 한 명 적은 $R(s-1,t) + R(s,t-1) - 1$명입니다. 빨강 쪽이 $R(s-1,t) - 1$명 이하이고 파랑 쪽도 $R(s,t-1) - 1$명 이하라면 이웃은 모두 합해 $R(s-1,t) + R(s,t-1) - 2$명 이하일 텐데, 실제로는 그보다 한 명 많습니다. 그러니 비둘기집 원리로 둘 중 하나는 반드시 일어나고

여섯 명 파티로 확인해 봅시다. $R(2, 3)$은 빨강 $K_2$(빨강 선 하나)나 파랑 삼각형이 반드시 생기는 가장 작은 수입니다. 빨강 선이 하나도 없으면 모든 선이 파랑이니 세 명이면 파랑 삼각형이 생기고, 두 명이면 선 하나를 파랑으로 칠해 둘 다 피할 수 있으니 $R(2, 3) = 3$입니다. 마찬가지로 $R(3, 2) = 3$이니 부등식은 $R(3, 3) \le 3 + 3 = 6$, 곧 앞의 증명 그대로입니다.

이 부등식으로 큰 램지 수의 상한⁠(upper bound)⁠을 차례로 쌓을 수 있습니다. 숫자로 한 번 해 봅시다. 빨강 선 하나만 피하면 되는 $R(2, 4)$는 4입니다. 빨강을 하나도 쓰지 않으면 모든 선이 파랑이라, 네 명이면 파랑 $K_4$가 생기고 세 명으로는 생기지 않기 때문입니다. 그러니

둘째 식에서는 색을 맞바꾸어도 문제가 같으니 $R(4, 3) = R(3, 4)$임을 썼습니다.

이렇게 나오는 수 3, 6, 10, 20은 파스칼의 삼각형⁠(Pascal's triangle)⁠에 있는 수입니다. 파스칼의 삼각형은 맨 위에 1을 놓고, 아래로 내려가며 한 칸의 수를 바로 위 두 칸의 합으로 채운 수의 표입니다. 위의 부등식도 '한 칸은 위의 두 칸의 합을 넘지 않는다'는 같은 모양입니다. 파스칼의 삼각형에서 m째 줄 r째 칸(둘 다 0부터 셉니다)의 수는 이항계수⁠(binomial coefficient)⁠ $\binom{m}{r}$('m개 중 r개'라고 읽습니다)로, m개 가운데 r개를 고르는 방법의 수입니다. 예를 들어 4개 가운데 2개를 고르는 방법은 $\binom{4}{2} = 6$가지입니다.

램지 수와 이항계수는 출발점이 같습니다. $R(s, 2) = s$, $R(2, t) = t$이고(앞의 $R(2, 4) = 4$와 같은 이유), 이항계수 쪽도 $\binom{s}{s-1} = s$, $\binom{t}{1} = t$입니다. 그다음부터 이항계수는 '위의 두 칸의 합'과 정확히 같고, 램지 수는 그 합을 넘지 못합니다. 그러니 한 단계씩 올라갈 때마다 램지 수는 이항계수를 넘지 못합니다. 이처럼 출발점에서 성립하고, 한 경우에서 성립하면 다음 경우에도 성립함을 보여 모든 경우를 확인하는 방법을 수학적 귀납법⁠(mathematical induction)⁠이라 합니다. 이렇게 얻는 결과는 다음과 같습니다.

앞의 숫자로 확인하면 $R(3, 3) \le \binom{4}{2} = 6$, $R(3, 4) \le \binom{5}{2} = 10$, $R(4, 4) \le \binom{6}{3} = 20$입니다.

이 값은 상한, 다시 말해 $R(s, t)$가 넘을 수 없는 위쪽 한계입니다. 두 색의 크기가 같은 대각선의 경우 $k =$ 일 때 이 상한은 명이고 실제 값은 상한은 대략 $4^k$의 빠르기로 자랍니다. 파스칼의 삼각형에서 $2k-2$째 줄의 수를 모두 더하면 $2^{2k-2} = 4^{k-1}$이고, 상한은 그 가운데 한 칸이니 $4^{k-1}$을 넘지 않습니다.

비교를 위해 아래쪽 한계도 적어 둡니다. 6절에서 볼 에르되시의 하한⁠(lower bound)⁠, 다시 말해 $R(k, k)$가 적어도 이보다는 크다는 값은 명입니다.

상한과 하한 사이가 이렇게 넓으니, 정확한 값은 놀랄 만큼 조금밖에 모릅니다. $R(4, 4) = 18$은 1955년 수학자 로버트 그린우드와 하버드의 앤드루 그리슨이 밝혔습니다. 17명의 좋은 색칠을 만드는 데에는 정수론⁠(number theory)⁠이 쓰였습니다. 제곱수⁠(perfect square)⁠ $1^2, 2^2, 3^2, \ldots$을 17로 나눈 나머지⁠(remainder)⁠로 나올 수 있는 수는 1, 2, 4, 8, 9, 13, 15, 16의 여덟 개뿐입니다(예를 들어 $6^2 = 36 = 2 \times 17 + 2$이니 나머지는 2입니다). 사람에게 0부터 16까지 번호를 붙이고, 두 번호의 차이를 17로 나눈 나머지가 이 여덟 수 가운데 하나일 때 아는 사이로 칠하면, 서로 다 아는 넷도 서로 다 모르는 넷도 없습니다(모듈러 연산⁠, modular arithmetic⁠). 그리슨은 2차 세계대전 때 미 해군에서 암호를 해독한 수학자였습니다. $R(4, 5) = 25$는 1995년 오스트레일리아 국립대학의 브렌던 매케이와 미국 로체스터 공과대학의 스타니스와프 라지소프스키가 컴퓨터로 확정했습니다. 매케이는 8절에서 전혀 다른 일로 다시 등장합니다.

$R(5, 5)$는 아직 모릅니다. 2020년대 중반 기준으로 알려진 것은 $43 \le R(5, 5) \le 46$입니다. 하한 43은 1989년에 찾은 42명의 색칠에서 나왔고, 상한 46은 2024년 매케이와 오스트레일리아 국립대학의 수학자 비글레이크 앙겔트바이트가 선형 계획법⁠(linear programming)⁠과 대규모 컴퓨터 계산을 엮어 48에서 끌어내렸습니다. 선형 계획법은 일차식으로 된 여러 조건을 지키면서 일차식 하나를 가장 크게 또는 작게 만드는 방법입니다. 많은 연구자는 답이 43이라고 짐작합니다. 43명만 되어도 색칠이 $2^{903}$가지라 모두 훑을 수는 없습니다. 지름길도 쉽게 나오지 않으리라는 짐작을 뒷받침하는 사실이 계산 이론⁠(theory of computation)⁠에 있습니다. 주어진 그래프에 서로 다 이어진 $k$개의 점이 있는지 묻는 문제는 1972년 컴퓨터 과학자 리처드 카프가 꼽은 NP-완전⁠(NP-complete)⁠ 문제의 하나입니다. NP-완전 문제는 답을 건네받으면 확인은 빨리 할 수 있지만, 빨리 찾는 방법은 알려져 있지 않은 문제들 가운데 가장 어려운 무리입니다(P 대 NP 문제⁠(P versus NP problem)⁠, 「기계가 풀 수 없는 문제」 7절).

비둘기집 원리는 1834년 디리클레가 정수론의 증명에 쓴 것이 이른 예로 흔히 꼽히고, 독일어로는 '서랍 원리⁠(drawer principle)⁠'라고 불렸습니다. 그러나 인쇄된 기록은 200년 앞섭니다. 1622년 로렌 지방 퐁타무송의 예수회 수사 장 뢰레숑은 수학 여러 분야의 명제를 모은 라틴어 책에서, 사람은 많고 머리카락 수에는 한계가 있으니 머리카락 수가 똑같은 두 사람이 반드시 있다고 적었습니다. 누가 그런지는 모르면서 있다는 것만 아는 논증이라는 점에서, 이 문장은 이 글의 정리들과 같은 모양입니다(「불가능의 증명」 6절에서 같은 원리가 압축과 정렬의 한계를 긋는 것을 볼 수 있습니다).

3 · 스물여섯 해프랭크 램지

이 절의 물음은 이것입니다. 이 수에 이름을 남긴 프랭크 램지는 어떤 사람이었고, 논리학자인 그가 왜 이 정리를 증명했을까? 답은 한 논리학 논문의 보조정리⁠(lemma)⁠에 있습니다.

램지 수에 이름을 준 사람은 이런 파티 문제를 한 번도 푼 적이 없습니다. 그는 논리학자였고, 철학자였고, 경제학자였습니다. 프랭크 플럼프턴 램지는 1903년 케임브리지에서 태어났습니다. 아버지는 모들린 칼리지의 부학장(President)을 지낸 수학 교사였고, 동생 마이클은 뒤에 캔터베리 대주교가 됩니다. 윈체스터 학교를 거쳐 트리니티 칼리지에서 수학을 공부한 그는 1923년 최우등 성적으로 졸업했습니다.

학부생 시절 그는 독일어를 빠르게 익혀, 열여덟, 열아홉 살에 오스트리아 출신의 철학자 비트겐슈타인이 쓴 『논리철학 논고』의 영어 번역 초고를 만들었습니다. 1922년 런던에서 나온 영어판에는 언어학자 C. K. 오그던의 이름이 번역자로 실렸지만, 초고의 대부분은 램지의 손에서 나왔습니다. 1923년에는 학술지 『마인드』에 이 책의 날카로운 서평을 실었고, 그해 가을에는 오스트리아의 산골 마을 푸흐베르크로 비트겐슈타인을 찾아갔습니다. 철학을 그만두고 초등학교 교사가 되어 있던 비트겐슈타인과 그는 2주 동안 책을 한 문장씩 함께 읽었습니다. 1929년 비트겐슈타인이 케임브리지로 돌아오도록 애쓴 사람도 램지와 경제학자 존 메이너드 케인스였습니다. 비트겐슈타인이 『논고』를 박사 논문으로 냈을 때, 형식상의 지도 교수는 그보다 열네 살 어린 램지였습니다.

케인스는 램지의 후원자이자 논쟁 상대였습니다. 1924년 램지가 킹스 칼리지의 펠로가 된 데에는 케인스의 힘이 컸습니다. 1926년 램지는 강연 「진리와 확률⁠(probability)⁠」에서 케인스의 확률론을 비판하며, 확률을 한 사람이 어떤 일에 거는 믿음의 정도로 보고 그것을 내기에 얼마를 걸겠느냐로 재자고 제안했습니다. 여기서 이런 논증이 나옵니다. 믿음이 확률의 규칙을 어기는 사람에게는, 그가 공정하다고 여기는 내기들만 묶어 팔아도 결과가 어떻게 되든 그가 돈을 잃도록 짤 수 있습니다. 예를 들어 내일 비가 올 확률도 0.6, 오지 않을 확률도 0.6이라고 믿는 사람은 '비가 오면 100원'짜리 표와 '비가 오지 않으면 100원'짜리 표를 각각 60원에 기꺼이 삽니다. 120원을 내고, 날씨가 어떻든 100원만 돌려받습니다. 확률을 빈도로 보는 쪽과 믿음으로 보는 쪽의 오래된 논쟁은 「도박판에서 온 편지」에 있습니다.

그는 경제학에도 오래 남는 논문 두 편을 썼습니다. 1927년의 「과세 이론에 대한 기여」는 정부가 필요한 세금을 거두면서 사회의 손실을 가장 작게 하는 규칙을 이끌어 냈습니다. 수요가 가격에 덜 민감한 물건, 곧 값이 올라도 사람들이 사는 양을 별로 줄이지 않는 물건에 더 높은 세율을 매겨야 한다는 것입니다. 이 생각은 오늘날 '램지 가격 결정⁠(Ramsey pricing)⁠'이라는 이름으로 전기, 철도, 우편처럼 규제받는 독점 기업의 요금을 정하는 데 쓰입니다. 1928년의 「저축의 수학적 이론」은 한 나라가 오늘 얼마를 쓰고 얼마를 미래를 위해 남겨야 하는지를 변분법⁠(calculus of variations)⁠으로 풀었습니다. 변분법은 수 하나가 아니라 함수⁠(function)⁠ 전체, 여기서는 해마다 얼마씩 쓸지를 정한 계획 전체를 골라 어떤 양을 가장 크게 만드는 방법입니다. 이 모형은 수십 년 뒤 경제 성장 이론의 기본 틀이 됩니다. 케인스는 이 논문을 두고 수리경제학에 대한 가장 놀라운 기여 가운데 하나라고 평했습니다.

램지 이론이 태어난 논문은 이런 관심사들 사이에서 나왔습니다. 1928년 12월 램지는 런던 수학회에서 「형식 논리의 한 문제에 대하여」를 읽었습니다. 결정 문제⁠(decision problem)⁠의 한 특수한 경우를 푼 논문이었습니다. 논리식은 '모든', '어떤 …가 있다', '그리고', '아니다' 같은 말과 기호로 짠 문장입니다. 예를 들어 '모든 x에 대해 x는 x와 같다'는 x가 사람이든 수든 언제나 참입니다. 반면 '어떤 x가 있어서 x는 x를 안다'는 '안다'라는 관계를 어떻게 읽느냐에 따라 참이 되기도 하고 거짓이 되기도 합니다.

결정 문제는 같은 해 힐베르트가 수리 논리학⁠(mathematical logic)⁠의 중심 문제로 꼽은 것입니다. 아무 논리식이나 주어졌을 때 그 식이 기호를 어떻게 읽든 언제나 참인지를 기계적인 절차로 가려내라는 문제입니다. 같은 말로, 그 식을 뒤집은 식(부정)을 참으로 만드는 읽기가 하나라도 있는지를 가려내라는 문제이기도 합니다. 이 문제가 어떤 꿈에서 나왔는지는 「기계가 풀 수 없는 문제」 3절에 있습니다. 램지가 다룬 것은 '어떤 것들이 있어서, 모든 것에 대해 …'의 모양으로 시작하는 식들입니다. '어떤 x가 있어서, 모든 y에 대해 x는 y를 안다'가 그런 식입니다. 램지는 이런 식을 참으로 만드는 읽기가 있는지를 가려내는 방법이 있다는 것을 보였습니다. 같은 해 괴팅겐의 파울 베르나이스와 모제스 쇤핑켈도 이 꼴의 식을 다룬 논문을 냈고, 그래서 오늘날 이 식들의 모임을 세 사람의 이름을 따 '베르나이스–쇤핑켈–램지 부류'라고 부릅니다. 램지는 증명의 한 단계에서 다음 정리가 필요했습니다.

무한 램지 정리⁠(infinite Ramsey theorem)⁠. 자연수⁠(natural number)⁠에서 $r$개씩 고른 모든 묶음을 유한 개의 색으로 칠하면, 자연수의 무한 부분집합(자연수 가운데 무한히 많은 수를 골라 모은 것)이 있어서 그 안에서 고른 $r$개짜리 묶음은 모두 같은 색입니다. $r = 2$이면 묶음은 선이고, "무한히 많은 사람이 모인 파티에는 서로 다 아는 무한히 많은 사람이나 서로 다 모르는 무한히 많은 사람이 있다"는 말이 됩니다. 유한한 파티 정리도 여기서 논증을 한 단계 더하면 따라 나옵니다.

무한한 경우의 증명은 2절의 논증을 끝없이 되풀이하는 것입니다($r = 2$, 두 색의 경우로 적습니다). 무한히 많은 사람 가운데 한 명 $a_1$을 고르면, 그에게서 나가는 선은 무한히 많고 색은 두 가지뿐이니 한 색의 선이 무한히 많습니다(무한 비둘기집 원리). 그 색의 이웃들만 남기고 나머지는 버립니다. 남은 무리에서 다시 한 명 $a_2$를 골라 같은 일을 합니다. 이렇게 얻은 $a_1, a_2, a_3, \dots$에는 저마다 '뒤에 오는 모든 사람과 이어진 색'이 하나씩 붙어 있습니다. 이 색 꼬리표도 두 가지뿐이니, 같은 꼬리표를 단 사람이 무한히 많습니다. 그들끼리는 모든 선이 그 한 색입니다. 그 가운데 두 사람 $a_i$와 $a_j$($i \lt j$)를 이은 선의 색은 먼저 뽑힌 $a_i$의 꼬리표가 정하기 때문입니다. $a_j$는 $a_i$를 뽑은 뒤 남긴 '그 색의 이웃' 가운데서 나왔으니까요.

램지는 논문 안에서 이 조합의 정리들이 그 자체로도 흥미롭다고 적어 두었습니다. 그 말대로 보조정리가 본 정리보다 오래 살아남았습니다. 8년 뒤 처치와 튜링은 결정 문제 전체는 풀 수 없다는 것을 보였고(「기계가 풀 수 없는 문제」), 램지가 푼 특수한 경우는 논리학 교과서의 한 줄로 남았습니다. 반면 보조정리는 조합론의 한 분야가 되었습니다. 램지 자신은 그것을 보지 못했습니다.

램지가 결정 문제에 닿은 길은 수학이 무엇 위에 서 있느냐는 철학의 물음에서 시작됩니다. 케임브리지에는 러셀과 화이트헤드가 1910–13년에 펴낸 『수학 원리』가 있었습니다. 수학 전체를 논리에서 이끌어 내려는 이 시도를 논리주의라 부릅니다. 스물두 살의 램지는 1925년 논문 「수학의 기초⁠(basics)⁠」에서 논리주의⁠(logicism)⁠를 구하려 했습니다. 러셀은 역설을 피하려고 대상에 층을 매기는 복잡한 타입 이론⁠(type theory)⁠을 쓰고, 그 때문에 생긴 불편을 '환원 공리⁠(axiom of reducibility)⁠'로 메웠습니다. 환원 공리는 층이 높은 성질마다 똑같은 대상들에 들어맞는 가장 낮은 층의 성질이 있다고 그냥 가정하는 공리⁠(axiom)⁠로, 논리의 진리로 보기는 어려웠습니다. 램지는 역설을 두 무리로 나누었습니다. 러셀의 역설⁠(Russell's paradox)⁠처럼 집합⁠(set)⁠과 원소⁠(element)⁠의 논리에서 나오는 것은 단순한 층 구분만으로 막았습니다. "나는 거짓말을 하고 있다" 같은 말의 뜻에서 나오는 것은 논리가 아니라 언어의 문제로 돌렸습니다. 그렇게 해서 환원 공리가 필요 없게 만들었습니다.

그러나 말년에는 논리주의를 버리고, 수학에서 무한을 조심해서 다루자는 독일의 수학자 헤르만 바일의 직관주의⁠(intuitionism)⁠ 쪽으로 기울었습니다. 논리주의, 수학을 기호 규칙의 체계로 보고 그 규칙에 모순이 없음을 증명하려 한 힐베르트의 형식주의⁠(formalism)⁠, 브라우어르와 바일의 직관주의가 맞선 기초 논쟁의 이야기는 「무한에도 크기가 있다」 7절에 있습니다.

4 · 수를 칠하기슈어와 반 데르 바르던

이 절의 물음은 이것입니다. 점과 선 대신 수 1, 2, 3, …을 몇 가지 색으로 칠해도 한 색 안에 반드시 질서가 생길까? 여기서 질서란 $x + y = z$ 같은 덧셈 관계나, 간격이 일정한 수열입니다.

램지보다 먼저, 점과 선이 아니라 수를 칠하는 쪽에서 같은 현상이 발견되었습니다. 가장 이른 예는 1892년 쾨니히스베르크의 힐베르트입니다. 다항식⁠(polynomial)⁠이 더 작은 다항식의 곱으로 쪼개지는지 연구하던 그는, 자연수를 유한 개의 색으로 칠하면 한 색 안에 일정한 덧셈 구조가 반드시 생긴다는 보조정리를 증명했습니다. 원하는 개수만큼의 간격 $d_1, d_2, \ldots$과 출발점 $a$가 있어서, $a$에 간격들을 골라 더한 수 $a,\ a + d_1,\ a + d_2,\ a + d_1 + d_2, \ldots$가 모두 같은 색이라는 것입니다. 예를 들어 $a = 1$, $d_1 = 2$, $d_2 = 5$이면 1, 3, 6, 8의 네 수입니다. 간격이 둘이면 이 네 수는 정사각형의 네 꼭짓점⁠(vertex)⁠처럼 짜이고, 셋이면 정육면체처럼 짜입니다. 그래서 이 정리를 흔히 '힐베르트의 정육면체 보조정리⁠(Hilbert's cube lemma)⁠'라 부릅니다.

다음 예는 덧셈 하나만 보는 더 단순한 정리입니다. 1부터 $N$까지를 몇 가지 색으로 칠하면, $N$이 충분히 클 때 $x + y = z$를 만족하는 같은 색의 수 $x, y, z$가 반드시 있습니다($x$와 $y$는 같은 수여도 됩니다). 1916년 베를린의 수학자 이사이 슈어가 증명해서 슈어의 정리라 부릅니다. 두 색이면 1부터 4까지는 {1, 4}와 {2, 3}으로 나눠 피할 수 있습니다. 1 + 1 = 2, 4 + 4 = 8, 1 + 4 = 5는 {1, 4} 밖이고, 2 + 2 = 4, 2 + 3 = 5, 3 + 3 = 6은 {2, 3} 밖입니다. 그러나 5까지 가면 피할 수 없습니다. 1을 빨강이라 하면 1 + 1 = 2이니 2는 파랑, 2 + 2 = 4이니 4는 빨강, 1 + 3 = 4이니 3은 파랑이어야 합니다. 그러면 5는 1 + 4 = 5 때문에 빨강일 수 없고, 2 + 3 = 5 때문에 파랑일 수도 없습니다.

슈어가 이 정리를 찾은 것은 페르마의 마지막 정리⁠(Fermat's Last Theorem)⁠ 때문이었습니다. $m$이 3 이상이면 $x^m + y^m = z^m$을 만족하는 양의 정수⁠(integer)⁠ $x, y, z$는 없다는 페르마의 주장으로, 당시에는 추측이었고 1994년에야 앤드루 와일스가 증명했습니다. 정수 방정식에 해가 없음을 보이는 흔한 길은 양변을 어떤 수로 나눈 나머지만 비교하는 것입니다. 소수 $p$로 나눈 나머지만 보는 식을 합동식⁠(congruence)⁠이라 하고, $x^m + y^m \equiv z^m \pmod p$로 적습니다. '양변을 $p$로 나눈 나머지가 같다'는 뜻이고, ≡는 '합동'이라 읽습니다.

슈어는 이 길이 막혀 있음을 보였습니다. $p$가 충분히 크면 이 합동식에는 $x, y, z$ 가운데 어느 것도 $p$로 나누어떨어지지 않는 해가 늘 있습니다. 그러니 나머지만 보아서는 페르마의 정리를 증명할 수 없습니다. 그 증명의 열쇠가 바로 위의 색칠 정리였습니다.

같은 무렵 네덜란드의 수학자 보데는 이런 추측을 남겼다고 전해집니다. 자연수를 두 가지 색으로 칠하면 한 색 안에 원하는 만큼 긴 등차수열, 곧 3, 7, 11, 15처럼 간격이 일정한 수열이 있지 않을까? 1926년 함부르크 대학에 머물던 스물세 살의 네덜란드 수학자 바르털 반 데르 바르던은 점심 자리에서 수학자 에밀 아르틴, 오토 슈라이어에게 이 추측을 이야기했습니다. 세 사람은 식사 뒤 아르틴의 연구실로 가서 칠판 앞에서 오후를 보냈고, 그날 증명의 골격이 나왔습니다. 반 데르 바르던은 이듬해 「보데의 추측의 증명」을 발표했습니다. 색이 몇 가지이든, 자연수를 유한 개의 색으로 칠하면 한 색 안에 원하는 만큼 긴 등차수열이 있다는 이 정리가 반 데르 바르던 정리⁠(van der Waerden's theorem)⁠입니다. 그는 1971년에는 그 오후를 한 단계씩 되짚은 회고를 썼습니다. 이 증명을 널리 알린 사람은 소련의 수학자 알렉산드르 힌친입니다. 그는 1940년대 후반에 쓴 작은 책 『정수론의 세 진주』의 첫 진주로 반 데르 바르던의 정리를 골라 그 증명을 한 걸음씩 풀어 썼습니다. 이 책이 여러 언어로 옮겨지면서 이 정리는 조합론의 고전이 되었습니다.

가장 작은 경우를 직접 해 봅시다. 1부터 $n =$ 까지의 칸을 빨강과 파랑으로 칠하되, 같은 색의 3항 등차수열(예를 들어 2, 5, 8처럼 간격이 같은 세 수)이 생기지 않게 하는 것이 목표입니다.

다시 모든 경우 세기

그런데 9칸이면 충분하다는 것을 컴퓨터 없이 보일 수 있을까요? 9라는 정확한 값은 어렵지만, '어떤 유한한 칸 수면 충분하다'는 것은 반 데르 바르던의 생각으로 보일 수 있고, 그 과정에서 수가 왜 폭발하는지도 보입니다. 두 색에서 길이 3인 등차수열을 찾는다고 해 봅시다.

1. 덩어리로 묶기. 수를 1–5, 6–10, 11–15, …처럼 다섯 개씩 묶어 한 덩어리로 봅니다. 한 덩어리를 칠하는 방법은 $2^5 = 32$가지입니다. 이 32가지를 '덩어리의 색'이라고 생각하면, 덩어리가 33개만 있어도 비둘기집 원리로 같은 색의 덩어리 두 개가 나옵니다. 다시 말해 칠한 무늬가 똑같은 두 덩어리입니다. 그 두 덩어리를 $B_1$, $B_2$라 하고, 둘 사이의 간격만큼 $B_2$에서 더 간 덩어리를 $B_3$이라 합시다. 세 덩어리는 덩어리 단위의 등차수열입니다.
2. 한 덩어리 안 보기. 한 덩어리의 앞 세 자리 가운데 두 자리 $i \lt j$는 같은 색입니다(세 자리에 두 색이니 비둘기집). 그 색을 빨강이라 합시다. 셋째 항이 될 자리 $k = 2j - i$는 많아야 $2 \times 3 - 1 = 5$라 같은 덩어리 안에 있습니다. $k$가 빨강이면 $i, j, k$가 그대로 빨강 등차수열이니, $k$가 파랑인 경우만 남습니다. $B_1$과 $B_2$는 무늬가 같으니 둘 다 $i$, $j$번째가 빨강, $k$번째가 파랑입니다.
3. 셋째 덩어리가 결정하기. 이제 $B_3$의 $k$번째 자리를 봅니다. 빨강이면 $B_1$의 $i$번째, $B_2$의 $j$번째, $B_3$의 $k$번째가 빨강 등차수열입니다(덩어리 간격에 $j - i$를 더한 간격이 두 번 이어집니다). 파랑이면 세 덩어리의 $k$번째 자리가 덩어리 간격으로 늘어선 파랑 등차수열입니다. 어느 쪽이든 한 색 등차수열이 생깁니다.

$B_1$, $B_2$를 앞 33개 덩어리에서 고르면 $B_3$은 65번째 덩어리 안에 있으니($B_2$가 많아야 33번째, 간격이 많아야 32), 1부터 $5 \times 65 = 325$까지면 충분합니다. 참값 9에 비하면 터무니없이 크지만, 유한하다는 것이 중요합니다. 길이를 하나 늘릴 때마다 '색의 수'가 이런 식으로 거듭제곱만큼 불어나니, 이 논증이 주는 경계는 상상할 수 없을 만큼 커집니다.

되추적은 재귀⁠(recursion)⁠로 적는 가장 단순한 알고리즘⁠(algorithm)⁠의 하나입니다. 9칸에서는 금방 끝나지만, 반 데르 바르던 수는 너무 빨리 커져서 조금만 키워도 컴퓨터가 손을 들고 맙니다. 반 데르 바르던의 원래 증명이 주는 상한은 더 심해서, 거듭제곱을 몇 겹으로 쌓아도 따라잡지 못하는 속도(아커만 함수라 불리는 함수의 빠르기)로 자라는 크기였습니다. 이 상한을 크게 줄이는 일은 1988년 이스라엘의 논리학자 사하론 셸라, 2001년 영국의 수학자 티머시 가워스 같은 사람들의 몫이었습니다. 그래도 참값이 얼마나 빨리 자라는지는 아직 모릅니다.

슈어와 반 데르 바르던은 나치 시대에 다른 길을 걸었습니다. 유대계였던 슈어는 1935년 나치 정권에 교수직을 빼앗겼고, 1939년 팔레스타인으로 건너가 2년 뒤 텔아비브에서 세상을 떠났습니다. 반 데르 바르던은 1930–31년에 낸 『현대 대수학』으로 대수학의 교과서를 새로 썼고, 1931년부터 라이프치히 대학 교수로 일했습니다. 나치 시대 내내 독일에 남았던 일은 전쟁 뒤 네덜란드에서 자리를 얻는 데 걸림돌이 되었고, 그는 1951년부터 취리히 대학에서 가르쳤습니다.

5 · 행복한 결말부다페스트 공원의 수학 모임

이 절은 평면에 아무렇게나 찍은 점들 속에 볼록한 도형이 반드시 숨어 있느냐는 물음을 다룹니다. 이 물음이 램지의 정리를 조합론의 한가운데로 데려왔습니다. 물음이 나온 곳부터 봅시다.

무대는 부다페스트입니다. 1929년 봄부터 부다페스트의 수학과 학생 몇 명이 매주 도시 공원의 '익명의 저자' 동상 아래 모여, 헝가리 출신 수학자 폴리아와 세게가 쓴 문제집의 문제를 함께 풀었다고 전해집니다. 처음에는 뒤에 정수론과 그래프 이론⁠(graph theory)⁠에서 이름을 남긴 투란 팔, 물리학을 공부하던 에스테르 클라인 같은 학생들이었고, 얼마 뒤 화학을 공부하던 세케레시 죄르지가, 이듬해에는 에르되시 팔이 합류했습니다. 대부분 유대계였던 이들은 1920년 헝가리가 만든 대학 정원법 아래에서 공부하고 있었습니다. 이 법은 민족별로 입학 정원을 나누어, 1910년대에 대학생의 15% 안팎이던 유대계 학생을 인구 비율인 6% 정도로 묶으려 했습니다. 20세기 유럽의 첫 반유대 법으로 흔히 꼽히고, 1928년에야 민족별 정원 조항이 빠졌습니다. 같은 도시의 부다페스트 공과대학에서는 쾨니그 데네시가 짝짓기의 정리를 증명하고 1936년 첫 그래프 이론 교과서를 내게 됩니다. 그 이야기는 「짝을 찾는 알고리즘」 2–3절에 있습니다.

1933년 무렵 물리학도 클라인이 이 모임에 한 가지 관찰을 들고 왔습니다. 평면 위에 어느 세 점도 한 직선 위에 있지 않은 다섯 점을 아무렇게나 찍으면, 그중 네 점은 반드시 볼록 사각형을 이룹니다. 볼록하다는 것은 움푹 들어간 곳이 없다는 뜻입니다. 정확히는 도형 안의 어느 두 점을 이어도 그 선분이 도형 밖으로 나가지 않는다는 뜻이고, 사각형이라면 두 대각선이 서로 만나는 모양입니다. 물음을 정확히 적으면 이렇습니다. 점을 아무렇게나 찍어도 점이 충분히 많으면 볼록 다각형⁠(convex polygon)⁠이 반드시 숨어 있을까? 아래에서 점을 끌어 확인해 보세요. 사각형을 찾을 것인지 오각형을 찾을 것인지 으로 고르고, 점의 수는 개입니다.

다음 것 보기 피하는 배치 새로 흩뿌리기

네 점으로는 볼록 사각형⁠(convex quadrilateral)⁠을 피할 수 있습니다. 삼각형 안에 점 하나를 두면 됩니다. 다섯 점이면 피할 수 없는 이유는 점들을 못이라 치고 가장 바깥을 고무줄로 둘러싸 보면 알 수 있습니다. 고무줄은 볼록한 모양으로 몇몇 점에만 걸립니다. 고무줄에 걸린 점이 다섯이나 넷이면 그중 넷이 바로 볼록 사각형입니다. 셋이면 삼각형 안에 두 점이 있고, 그 두 점을 잇는 직선은 삼각형의 꼭짓점 하나를 한쪽에, 둘을 다른 쪽에 남깁니다. 두 꼭짓점이 있는 쪽의 두 점과 안의 두 점이 볼록 사각형입니다.

세케레시와 에르되시는 이 관찰을 일반화했습니다. 볼록 $n$각형을 보장하려면 점이 몇 개 있어야 할까? 그런 개수가 있기는 하다는 것을 보이기 위해 세케레시는 램지의 정리를 스스로 다시 발견했다고 합니다. 1935년 두 사람이 발표한 논문 「기하학의 한 조합 문제」는 램지 이론의 두 번째 출발점이 되었습니다. 두 사람은 $2^{n-2} + 1$개면 충분하다고 추측했습니다. $n = 4$이면 5개, 오각형이면 9개입니다. 위 그림에서 ‘피하는 배치’를 누르면 볼록 오각형이 없는 8개의 점이 나옵니다. 여기에 점을 하나 더하면 어디에 두어도 오각형이 생깁니다. 점이 16개이면서 볼록 육각형이 없는 배치는 1961년 에르되시와 세케레시가 이미 만들어 두었습니다. 거꾸로 점이 17개면 볼록 육각형이 반드시 생긴다는 것은 2006년에야 컴퓨터로 확인되었습니다. 이 계산을 함께한 사람이 말년의 세케레시였고, 논문은 그가 세상을 떠난 이듬해에 실렸습니다. 일반적인 $n$에 대한 추측은 아직 풀리지 않았습니다.

같은 논문에는 또 하나의 유명한 정리가 있습니다. 서로 다른 수 $n^2 + 1$개를 아무 순서로 늘어놓으면, 그 안에서 차례를 지키며 몇 개를 골라 길이 $n + 1$인 증가하는 수열이나 감소하는 수열을 반드시 만들 수 있습니다. 이렇게 골라낸 수열을 부분수열⁠(subsequence)⁠이라고 합니다. $n = 2$이면 수 5개에서 길이 3짜리를 찾습니다. 예를 들어 3, 1, 4, 5, 2에서는 3, 4, 5가 증가하는 부분수열입니다. 수가 4개($n^2$개)뿐이면 3, 4, 1, 2처럼 늘어놓아 피할 수 있습니다. 여기서 가장 긴 증가 부분수열(3, 4나 1, 2)도, 가장 긴 감소 부분수열(3, 1이나 4, 2 등)도 길이 2입니다. 아래에서 $n =$ , 수의 개수는 입니다. 막대 끝의 점을 위아래로 끌어 수의 순서를 바꿔 보세요.

섞기 n²개로 피하기

증명은 다시 비둘기집입니다. 각 수에 꼬리표 $(i, d)$를 붙입니다. $i$는 그 수에서 끝나는 가장 긴 증가 부분수열의 길이, $d$는 가장 긴 감소 부분수열의 길이입니다. 앞의 수 $a$가 뒤의 수 $b$보다 작으면 $a$에서 끝나는 증가 수열 뒤에 $b$를 붙일 수 있으니 $b$의 $i$가 더 크고, 크면 같은 이유로 $d$가 더 큽니다. 그러니 두 수의 꼬리표가 같을 수는 없습니다. 3, 1, 4, 5, 2로 해 보면 꼬리표는 차례로 (1, 1), (1, 2), (2, 1), (3, 1), (2, 2)이고, 모두 다릅니다. 오른쪽 그림에서 한 칸에 두 수가 들어가는 일이 없는 것을 보세요. 모든 꼬리표가 $n$ 이하라면 회색 칸은 $n^2$개뿐이니, $n^2 + 1$개의 수 가운데 적어도 하나는 노란 띠로 밀려납니다. 그 수에서 끝나는 길이 $n+1$의 단조 부분수열⁠(monotone subsequence)⁠, 곧 증가하거나 감소하는 부분수열이 있다는 뜻입니다. ‘n²개로 피하기’는 7 8 9 4 5 6 1 2 3처럼 증가하는 덩어리를 내림차순으로 쌓아, 회색 칸을 정확히 하나씩 채웁니다.

가장 긴 증가 부분수열을 실제로 찾는 일은 컴퓨터 과학의 단골 문제입니다. 꼬리표를 앞에서부터 차례로 계산하는 방법이 동적 계획법⁠(dynamic programming)⁠이고, 카드를 여러 더미로 나눠 쌓는 '인내심 정렬⁠(patience sorting)⁠'로 더 빨리 셀 수도 있습니다. 비교로 줄을 세우는 정렬의 방법들과 그 한계는 「줄 세우기의 한계」에 있습니다.

에르되시는 이 문제에 '행복한 결말 문제⁠(happy ending problem)⁠'라는 이름을 붙였습니다. 문제를 낸 클라인과 풀이에 매달린 세케레시가 1937년에 결혼했기 때문입니다. 결말까지의 길은 순탄하지 않았습니다. 유대계였던 부부는 1939년 무렵 나치를 피해, 당시 비자 없이 들어갈 수 있던 몇 안 되는 곳인 상하이로 건너갔습니다. 세케레시는 가죽 공장의 화학자로 일했고, 부부는 일본군 점령 아래 훙커우의 피난민 거리에서 전쟁을 견뎠습니다. 1948년 세케레시가 애들레이드 대학에 자리를 얻어 가족은 오스트레일리아로 건너갔고, 1960년대 초에는 시드니의 뉴사우스웨일스 대학으로 옮겼습니다. 클라인은 시드니의 매쿼리 대학에서 가르치며 고등학생을 위한 수학 모임을 꾸렸습니다. 두 사람은 2005년 8월 28일 애들레이드에서 한 시간 사이로 함께 세상을 떠났습니다.

1885년부터 오늘까지. 위의 연표에서 수학 줄(파랑)의 사건⁠(event)⁠이 케임브리지와 함부르크, 부다페스트에서 시작해 1990년대 이후 캔버라, 로스앤젤레스, 리우데자네이루로 퍼지는 것을 보세요. 지도의 노란 선과 분홍 선은 사람의 이동입니다. 부다페스트에서 상하이를 거쳐 애들레이드로 간 길, 베를린에서 텔아비브로 간 슈어의 망명길이 1930년대 유럽의 사정을 말해 줍니다. 주황 선은 생각이 건너간 길입니다.

6 · 동전을 던져 증명하기에르되시의 확률적 방법⁠(probabilistic method)⁠

2절에서 $R(k, k)$가 대략 $4^k$를 넘지 않는다는 것을 보았습니다. 이 절의 물음은 그 반대입니다. $R(k, k)$는 적어도 얼마나 클까요? 그것을 보이려면 한 색 $K_k$가 없는 큰 색칠을 실제로 내놓아야 합니다. 쉽게 떠오르는 방법은 이렇습니다. 사람들을 $k-1$명씩 $k-1$개의 모둠으로 나누고, 같은 모둠 안은 빨강, 다른 모둠 사이는 파랑으로 칠합니다. 빨강 $K_k$는 한 모둠 안에 $k$명이 있어야 하고, 파랑 $K_k$는 모둠이 $k$개 있어야 하니, 둘 다 없습니다. $k = 3$이면 네 사람을 두 명씩 두 모둠으로 나눈 것이고, 빨강 선은 모둠 안의 두 개뿐, 파랑 선은 모둠 사이의 네 개로 네모 모양을 이루니 어느 색에도 삼각형이 없습니다. 그래서 $R(k, k) > (k-1)^2$입니다. 하지만 이것은 $k$의 제곱일 뿐이고, 상한 $4^k$는 지수함수⁠(exponential function)⁠입니다. 차이가 너무 큽니다.

1947년 에르되시는 세 쪽짜리 논문 「그래프 이론에 관한 몇 가지 소견」에서 전혀 다른 길을 냈습니다. 좋은 색칠을 만들지 말고, 선마다 동전을 던져 색을 정하자는 것입니다. 그렇게 만든 무작위 색칠에서 한 색 $K_k$는 평균⁠(mean)⁠ 몇 개 생길까요? 같은 실험을 아주 많이 되풀이했을 때의 평균을 기댓값⁠(expected value)⁠이라 합니다.

세 단계로 셉니다. 첫째, $k$명을 고르는 방법은 $\binom{n}{k}$가지입니다. 둘째, 고른 $k$명 사이에는 선이 $\binom{k}{2}$개 있고, 선마다 빨강일 확률이 1/2이니 모두 빨강일 확률은 1/2을 $\binom{k}{2}$번 곱한 $2^{-\binom{k}{2}}$입니다($2^{-m}$은 $1/2^m$을 뜻합니다). 모두 파랑일 확률도 같으니, 한 색일 확률은 $2 \cdot 2^{-\binom{k}{2}}$입니다. $k = 3$이면 선 3개가 모두 같은 색일 확률이 $2 \times 1/8 = 1/4$입니다. 셋째, 무리마다 '한 색이면 1, 아니면 0'을 세어 더한 것이 한 색 $K_k$의 개수이고, 합의 기댓값은 기댓값의 합이므로(무리들이 선을 나눠 가져 서로 얽혀 있어도 그렇습니다) 무리의 수에 확률을 곱하면 됩니다.

입니다($n =$ , $k =$ ). $k = 3$, $n = 5$로 계산하면 $\binom{5}{3} \times \frac{1}{4} = 10 \times \frac{1}{4} = 2.5$개입니다. 이 값이 1보다 작다면 어떻게 될까요? 개수는 0, 1, 2, …처럼 정수이므로, 평균이 1보다 작으려면 0개인 색칠이 적어도 하나 있어야 합니다. 모든 색칠이 한 색 $K_k$를 하나 이상 가졌다면 평균도 1 이상이었을 테니까요. 색칠을 하나도 보여 주지 않고, 그런 색칠이 있다는 것만 증명한 것입니다.

다시 던지기 300번 던지기

어림셈을 해 봅시다. $\binom{n}{k}$는 $n^k/k!$보다 작습니다. 여기에 $n = 2^{k/2}$을 넣으면 $n^k = 2^{k^2/2}$이고, 뒤의 $2^{1 - k(k-1)/2}$와 곱하면 지수의 $k^2/2$가 지워져 기댓값은 $2^{1+k/2}/k!$보다 작아집니다. 이 값은 $k = 3$에서 이미 1보다 작고, $k$가 커질수록 분모의 계승⁠(factorial)⁠ $k! = k \times (k-1) \times \cdots \times 1$이 분자보다 훨씬 빨리 커져서 빠르게 0으로 갑니다. 예를 들어 $k = 10$, $n = 32$이면 기댓값은 약 $3.7 \times 10^{-6}$입니다. 32명의 파티에서 서로 다 아는 열 명도, 서로 다 모르는 열 명도 없게 관계를 짜는 방법이 있다는 뜻입니다. 그래서

($\sqrt{2}^{\,k}$은 '루트 2의 $k$제곱'으로, $2^{k/2}$과 같은 수입니다. $k = 10$이면 32입니다.) 정리하면, 하한은 동전 던지기로, 상한은 비둘기집으로 얻었고, 둘 다 $k$에 대해 지수적으로 자라지만 밑이 $\sqrt2 \approx 1.41$과 4로 다릅니다.

제곱 수준이던 하한이 단숨에 지수 수준이 되었습니다. 에르되시 자신은 이것을 확률의 말이 아니라 "한 색 $K_k$가 있는 색칠의 수가 전체 색칠의 수보다 적다"는 세기의 말로 적었지만, 생각은 같습니다. 같은 생각을 먼저 쓴 사람도 있습니다. 1943년 헝가리의 수학자 셀레 티보르는 선수 $n$명이 모두 한 번씩 겨루는 리그전을 생각했습니다. 모든 선수를 '앞 사람이 바로 뒷사람을 이긴' 차례로 한 줄로 세우는 방법을 세면, 그 수가 적어도 $n!/2^{n-1}$가지인 대진 결과가 있습니다. 셀레는 이것을 경기마다 동전을 던져 승부를 정했을 때의 평균으로 보였고, 흔히 이 논증을 확률적 방법의 첫 예로 꼽습니다. 무작위로 고른 대상이 원하는 성질을 지닐 확률이 0보다 크면 그런 대상은 존재합니다. 이 증명법이 확률적 방법이고, 에르되시는 평생 이 방법을 조합론, 정수론, 기하학 곳곳에 퍼뜨렸습니다. 그가 헝가리의 수학자 레니 얼프레드와 함께 연구한 무작위 그래프⁠(random graph)⁠와 에르되시 수⁠(Erdős number)⁠ 이야기는 「일곱 다리의 도시」에 있습니다.

이 증명에는 이상한 구석이 있습니다. 동전을 던지면 거의 확실히 좋은 색칠이 나오는데, 막상 규칙으로 만들어 보이라고 하면 아무도 못 합니다. $\sqrt{2}^{\,k}$에 가까운 크기의 좋은 색칠을 명시적으로 짓는 문제는 70년 넘게 열려 있고, 연구자들은 이를 "건초 더미에서 건초 찾기"라고 부르기도 합니다. 이 문제는 무작위처럼 보이는 수열을 우연 없이 정해진 규칙만으로(결정론적으로) 만드는 일, 곧 무작위 알고리즘⁠(randomized algorithm)⁠에서 우연을 걷어 내는 연구와 이어져 있습니다.

경계는 오래 움직이지 않았습니다. 1935년의 상한 $4^k$는 거의 90년 동안 밑이 줄지 않았습니다. 2023년 3월 리우데자네이루의 순수·응용수학 연구소(IMPA)와 케임브리지의 네 수학자 캄푸스, 그리피스, 모리스, 사하스라부데는 어떤 작은 양수 $\varepsilon$('엡실론')에 대해 $R(k, k) \le (4 - \varepsilon)^k$임을 보였습니다. 밑 4가 처음으로 줄어든 것입니다. 뒤이은 연구들은 밑을 3.8 근처까지 내렸다고 보고했습니다. 하한의 밑 $\sqrt{2}$는 2020년대 중반 기준으로도 넘어서지 못했습니다. 두 색의 크기가 다른 경우에는 2025년에 1947년의 하한을 지수적으로 개선했다는 결과가 나왔지만, 대각선의 경우는 여전히 에르되시의 동전이 가장 좋은 답입니다.

에르되시는 이 어려움을 이야기로 들려주곤 했다고 전해집니다. 미국의 수학자 조엘 스펜서가 1990년대의 강의록 등에서 옮긴 내용을 풀어 쓰면 이렇습니다.

우리보다 훨씬 강한 외계의 군대가 지구에 내려와 $R(5, 5)$의 값을 대지 않으면 지구를 없애겠다고 한다면, 우리는 모든 컴퓨터와 모든 수학자를 모아 그 값을 찾아야 한다. 그러나 그들이 $R(6, 6)$을 요구한다면, 외계인을 없애려 애쓰는 편이 낫다.— 에르되시의 이야기로 전해지는 것. 조엘 스펜서, 『확률적 방법에 관한 열 개의 강의』(1994) 등

7 · 밀도의 정리소수 속의 등차수열

이 절의 물음은 이것입니다. 긴 등차수열을 보장하는 것은 '색칠'일까, 아니면 단지 '수가 많다는 것'일까? 반 데르 바르던의 정리는 "자연수를 몇 가지 색으로 나누면 어느 한 색에 긴 등차수열이 있다"고 말합니다. 1936년 에르되시와 투란은 더 강한 질문을 던졌습니다. 색은 상관없고, 한 집합이 충분히 많은 자연수를 담고 있기만 하면 긴 등차수열이 있지 않을까? 여기서 '충분히 많다'는 1부터 $N$까지 가운데 그 집합에 드는 수의 비율, 곧 밀도가 $N$이 커져도 0으로 줄지 않는다는 뜻입니다. 엄밀히는 비율이 한 값으로 모이지 않을 수도 있어서, '비율이 어떤 양수 이상으로 끝없이 되풀이해 올라온다'는 뜻으로 씁니다. 이것을 상밀도가 양수라고 합니다. 예를 들어 짝수는 늘 절반이니 밀도가 1/2이고, 제곱수 1, 4, 9, …는 1부터 $N$까지에 약 $\sqrt N$개뿐이라 비율 $\sqrt N / N$이 0으로 줄어듭니다. 색이 유한 개이면 그중 한 색은 밀도가 양수이니, 이 질문이 참이면 반 데르 바르던의 정리가 따라 나옵니다.

답은 조금씩 나왔습니다. 1953년 런던의 수학자 클라우스 로스는 푸리에 급수(복잡한 무늬를 규칙적인 물결들의 합으로 나누어 보는 방법)의 방법으로 길이 3인 경우를 증명했습니다. 모든 길이의 답은 1975년 부다페스트의 수학자 세메레디 엔드레가 순수한 조합론의 논증으로 냈고, 에르되시가 걸어 둔 1,000달러의 상금을 받았습니다. 세메레디의 증명은 너무 복잡해서, 새 분야를 연 것은 오히려 2년 뒤 이스라엘의 수학자 힐렐 푸르스텐베르크가 전혀 다른 도구인 에르고딕 이론⁠(ergodic theory)⁠으로 해낸 두 번째 증명이었습니다. 에르고딕 이론은 시간에 따라 움직이는 계(동역학계⁠(dynamical system)⁠)가 오랫동안 움직일 때 그 평균적인 모습을 연구하는 분야입니다. 세메레디는 2012년 노르웨이 정부가 주는 수학상인 아벨상을 받았습니다.

소수는 이 정리가 닿지 않는 곳에 있었습니다. 소수 정리⁠(prime number theorem)⁠에 따르면 $N$ 근처에서 소수의 비율은 $1/\ln N$ 정도이고, $N$이 커지면 0으로 줄어듭니다. 여기서 $\ln N$('엘 엔 N')은 자연로그⁠(natural logarithm)⁠로, 약 2.718인 수 e를 몇 번 곱해야 $N$이 되는지를 나타냅니다. 100만 근처에서는 $\ln N$이 약 14이니, 수 14개에 하나꼴로 소수입니다. 밀도가 0인 집합이니 세메레디의 정리를 쓸 수 없습니다. 그래도 소수 속의 등차수열은 쉽게 눈에 띕니다. 3, 5, 7이 있고, 5, 11, 17, 23, 29(간격 6)가 있고, 7, 37, 67, 97, 127, 157(간격 30)이 있습니다. 2004년 영국의 수학자 벤 그린과 오스트레일리아 출신의 테런스 타오는 소수만으로 된 등차수열이 원하는 만큼 길게 있다는 것을 증명했습니다. 소수가 충분히 '무작위처럼' 흩어져 있어서 밀도가 양수인 집합처럼 다룰 수 있다는 것을 보인 것이 핵심이었습니다. 타오는 2006년, 40세 이하의 수학자에게 주는 가장 권위 있는 상인 필즈상⁠(Fields Medal)⁠을 받았습니다. 정리는 존재만 보장할 뿐이어서, 컴퓨터로 실제로 찾은 가장 긴 예는 2020년대 기준으로 스물몇 항에 머뭅니다. 소수의 분포를 세어 온 긴 역사는 「소수를 세는 사람들」에 있습니다.

에르되시는 더 대담한 추측도 남겼습니다. 자연수의 집합에서 원소의 역수⁠(inverse)⁠의 합이 무한대로 커지면, 그 집합에는 임의 길이의 등차수열이 있다는 것입니다. 모든 자연수의 역수의 합인 조화급수⁠(harmonic series)⁠가 발산⁠(divergence)⁠하듯, 소수의 역수의 합도 발산한다는 것을 18세기에 오일러가 보였습니다. 그러니 그린–타오 정리⁠(Green–Tao theorem)⁠는 이 추측의 한 특수한 경우입니다. 추측 전체는 아직 열려 있습니다. 쌍둥이 소수⁠(twin primes)⁠처럼 간격이 작은 소수 쌍을 묻는 문제와는 다른 방향의 질문입니다.

8 · 무늬를 보는 눈우연 속의 질서

램지 이론의 교훈을 한 문장으로 줄인 말이 있습니다. "완전한 무질서는 불가능하다." 흔히 베를린에서 태어나 예루살렘과 미국에서 일한 수학자 테오도어 모츠킨의 말로 전해집니다. 아무리 무작위로 만든 것이라도 충분히 크면 그 안에 규칙적인 조각이 반드시 들어 있다는 뜻입니다. 이 절의 물음은 이것입니다. 무늬가 어디에나 있다면, 무늬를 찾았다는 것은 무엇을 증명할까? 아래 그림은 동전 개를 던진 결과를 빨강과 파랑으로 줄지어 놓은 것입니다. 컴퓨터가 그 안에서 같은 색으로만 된 가장 긴 등차수열을 찾아 노란 선으로 이어 줍니다.

지금 찾은 가장 긴 것은 개짜리, 입니다. 같은 면이 연달아 나온 가장 긴 줄(간격 1)은 개입니다. 다시 던지기 동전 수를 늘려 보세요. 가장 긴 등차수열은 대략 $2\log_2 N$ ≈ 근처에서 천천히 자랍니다. $\log_2 N$은 2를 몇 번 곱해야 $N$이 되는지를 뜻하니($\log_2 1024 = 10$), 동전 수를 두 배로 늘려도 이 값은 2만 늡니다. 길이 $L$인 등차수열의 후보는 $N^2$에 비례할 만큼 많고, 후보 하나가 모두 같은 면일 확률은 $2^{1-L}$이므로, 둘을 곱해 1쯤이 되는 곳이 로그의 두 배이기 때문입니다.

이 사실은 수학 밖에서 실제로 문제가 된 적이 있습니다. 1994년 이스라엘의 연구자 비츠툼, 립스, 로젠베르크는 통계학⁠(statistics)⁠ 학술지 『통계 과학』에 논문 한 편을 실었습니다. 창세기의 히브리어 원문을 일정한 간격으로 건너뛰며 읽으면 후대 랍비들의 이름과 생몰일이 서로 가까이 나타난다는 내용이었습니다. 일정한 간격으로 건너뛴 글자들은 바로 글자 위의 등차수열입니다. 1997년 기자 마이클 드로스닌의 책 『바이블 코드』가 이 방법으로 암살 사건들이 '예언'되어 있다고 주장해 베스트셀러가 되었습니다. 드로스닌이 비판자들에게 『모비 딕』에서 총리 암살 예언을 찾아보라고 하자, 2절에 나온 매케이가 같은 방법으로 『모비 딕』에서 인디라 간디, 이츠하크 라빈, 존 F. 케네디 등의 암살 '예언'을 찾아냈습니다. 1999년 매케이와 수학자 드로르 바르나탄, 심리학자 마야 바르힐렐, 수학자 길 칼라이는 『통계 과학』에 반박 논문을 실었습니다. 이름의 철자와 표기를 고르는 자유가 그 결과를 만들어 냈고, 같은 자유를 쓰면 『전쟁과 평화』의 히브리어 번역도 창세기만큼 '예언'한다는 것을 보인 논문입니다.

램지 수를 컴퓨터로 계산하던 사람이 성경 암호를 반박한 것은 우연이 아닙니다. 두 일은 같은 질문을 다룹니다. 충분히 큰 글 속에 무늬가 있다는 것은 아무 증거도 되지 않습니다. 무늬는 어디에나 있어야 하니까요. 중요한 것은 그 무늬가 무작위의 글에서 기대되는 것보다 많은지이고, 그것을 따지려면 몇 번이나 찾아보았는지까지 세어야 합니다. 서른 명의 반에 생일이 같은 두 사람이 있을 확률이 70%를 넘는다는 생일 문제⁠(birthday problem)⁠도 같은 교훈을 줍니다. 한 쌍을 미리 정하면 드문 일이지만, 모든 쌍을 뒤지면 흔한 일입니다.

사람의 눈은 이런 계산을 하지 않습니다. 1958년 독일의 정신의학자 클라우스 콘라트는 조현병 초기의 환자들이 아무 관계 없는 일들 사이에서 의미 있는 연결을 보는 경험을 '아포페니아⁠(apophenia)⁠'라고 불렀습니다. 지금 이 말은 우연에서 무늬를 읽어 내는 사람의 일반적인 성향을 가리키는 데도 쓰입니다. 밤하늘의 별을 이어 별자리를 만든 것도, 주가 그래프에서 '머리어깨형'을 찾는 것도, 한동네에 병이 몰린 것에서 원인을 찾는 것도 같은 눈입니다. 그 가운데 일부는 진짜 원인을 가리키고 일부는 우연입니다. 둘을 가르는 도구가 통계이고, 겉보기 상관관계⁠(correlation)⁠가 원인을 뜻하지 않는다는 이야기는 「담배와 폐암」에 있습니다.

그렇다면 '무작위'란 무엇일까요? 1960년대 콜모고로프와 미국의 수학자 그레고리 차이틴은 짧게 적을 수 없는 문자열을 무작위라고 정의했습니다(콜모고로프 복잡도⁠, Kolmogorov complexity⁠). 이 정의로 보면 무작위 문자열도 긴 한 색 등차수열을 품고 있지만, 그것은 문제가 되지 않습니다. 모든 문자열에 반드시 있는 무늬는 그 문자열에 대해 아무 정보도 주지 않으므로, 압축에 쓸 수 없기 때문입니다. 무늬와 정보의 이 차이는 「짧게 보내기」로 이어집니다.

램지 이론은 수학의 기초에도 흔적을 남겼습니다. 1977년 맨체스터의 논리학자 제프 파리스와 버클리의 레오 해링턴은 유한한 램지 정리를 조금 강하게 바꾼 명제가, 자연수의 기본 공리들을 모은 페아노 산술⁠(Peano arithmetic)⁠로는 증명할 수 없다는 것을 보였습니다. 이 명제는 더 강한 집합론⁠(set theory)⁠의 공리로는 증명되므로, 참이라는 것은 압니다. 바꾼 곳은 한 군데입니다. 번호가 붙은 점들을 칠했을 때 한 색으로만 이어진 무리를 찾되, 그 무리의 점 개수가 무리 안의 가장 작은 번호보다 크거나 같아야 한다는 조건을 덧붙입니다. 예를 들어 3, 5, 7, 9번 점의 무리는 점이 4개이고 가장 작은 번호가 3이니 조건을 지키지만, 10, 20, 30번의 무리는 점이 3개뿐이라 지키지 못합니다. 그 명제가 보장하는 수가 너무 빨리 자라서, 산술의 공리들이 따라가지 못하는 것입니다. 이 명제는 괴델의 불완전성 정리⁠(incompleteness theorem)⁠가 말하는 '참이지만 증명할 수 없는 문장'이, 인공적인 자기 지시 문장이 아니라 평범한 조합론의 명제로 나타난 첫 예로 꼽힙니다. 무언가를 증명할 수 없다는 것을 증명하는 방법은 「불가능의 증명」 5절에 있습니다. 램지가 논리학의 문제를 풀다 만든 도구가 50년 뒤 논리학의 한계를 보여 준 셈입니다.

9 · 이어지는 길질서가 숨는 곳

"충분히 크면 질서가 생긴다"는 생각은 여러 분야로 이어집니다.

• 그래프: 선을 칠하는 대신 점을 칠하면 4색 정리⁠(four color theorem)⁠ 같은 채색 문제가 됩니다. 램지 수를 다루는 말들, 완전 그래프⁠(complete graph)⁠와 차수와 이웃은 모두 「일곱 다리의 도시」의 그래프 이론에서 왔습니다. 4색 정리의 첫 '증명'으로 11년 동안 받아들여졌던 1879년 켐프의 논증과 그 빈틈은 「틀린 증명이 만든 수학」 4절에 있습니다.
• 게임: 심 게임이 비기지 않는 까닭이 여섯 명의 파티 정리이듯, 헥스가 비기지 않는다는 사실은 고정점 정리⁠(fixed-point theorem)⁠와 같은 내용입니다. 무한 램지 정리처럼 끝없는 대상을 다루는 게임에서 반드시 이기는 쪽이 있느냐는 물음은 집합론의 공리 문제로 이어집니다(「이기는 쪽이 존재한다」).
• 세기: 램지 수의 상한은 이항계수로, 하한은 기댓값으로 셌습니다. 비둘기집 원리와 순열⁠(permutation)⁠, 세지 않고 세는 여러 기술은 「세지 않고 세기」에 모여 있습니다.
• 짝짓기: 부다페스트의 쾨니그가 1931년에 증명한 이분 그래프⁠(bipartite graph)⁠의 정리와 홀의 정리⁠(Hall's theorem)⁠도 "충분히 많으면 반드시 있다"는 꼴의 정리입니다. 에르되시와 세케레시가 자란 헝가리 조합론의 전통이 「짝을 찾는 알고리즘」으로 이어집니다.
• 확률: 확률적 방법은 존재를 보이는 데 확률을 씁니다. 반대로 큰 수의 법칙⁠(law of large numbers)⁠은 무작위 속에서 평균이라는 질서가 나타나는 모습입니다(「도박판에서 온 편지」).
• 계산: 램지 수의 계산이 막히는 이유는 P 대 NP 문제와 이어지고, 파리스–해링턴 정리⁠(Paris–Harrington theorem)⁠는 정지 문제⁠(halting problem)⁠와 불완전성이 사는 논리의 세계에 속합니다(「기계가 풀 수 없는 문제」).
• 무한: 무한 램지 정리는 가산 집합⁠(countable set)⁠에 대한 정리이고, 더 큰 무한에서 같은 정리가 성립하는지는 큰 기수⁠(large cardinal)⁠ 이론, 곧 집합론의 보통 공리로는 있다는 것을 증명할 수 없을 만큼 큰 무한을 다루는 분야로 이어집니다(「무한에도 크기가 있다」, 집합의 크기⁠(cardinality)⁠).
• 또 다른 무질서: 램지 이론의 무질서는 '아무렇게나 칠한 것'입니다. 규칙은 완벽히 정해져 있는데도 앞을 내다볼 수 없는 혼돈⁠(chaos)⁠은 전혀 다른 뜻의 무질서입니다(「나비의 날갯짓」).