Ramsey Number와 Erdos 아저씨의 재치

수학의 오묘한 점은 수학을 이루는 수 많은 정리들은 우리 삶의 상당히 사소한 부분까지 설명할 수 있다는 점이다.

어느 날 나는 저녁 식사에 아는 사람들을 5명을 초대했다. 우습게도 나도 그 5명 모두를 잘 알지는 못하고, 5명 중에도 친한 사람이 있고 처음 보는 사람이 있다. 식탁에 둘러 앉은 나를 포함한 6명 간의 관계를 아래 그림과 같이 표현할 수 있다. 두 사람 사이에 선을 긋는데 그 선의 색은 다음과 같은 법칙을 따른다: 둘이 서로 알면 둘 사이를 빨간 색으로 칠하고, 둘이 모르는 사이면 파란색으로 칠한다.

이런 식으로 선을 그어서 살펴보면, "언제나" 3명의 서로 친한 또는 3명의 서로 모르는 관계가 생긴다는 것을 확인할 수 있다. 쉽게 얘기하자면 위의 그림에서는 색을 어떻게 칠하던 빨간색과 파란색만을 써서 관계를 표시할 경우, 무조건 3명의 서로 친한 사람이 있거나 3명의 서로 모르는 관계가 생긴다는 것이다. 삼각형. 빨간색일 수도 있고 파란색일 수도 있지만, 한 색으로 칠해진 삼각형이 무조건 생긴다!

우습게도 이런 사소한 점도 수학의 정리 중 하나로 존재한다. Frank P. Ramsey라는 26세에 요절한 한 수학자가 문제를 풀던 중 증명 과정에서 살짝 언급한 Ramsey's theorem (당시 Ramsey는 lemma 중 하나로 정리해놨다고 한다)이 그것이다. 아래의 theorem의 n에 6을 넣고 r에 3을 넣어보면 위의 저녁 식탁의 문제에 대한 답이다.

Ramsey's theorem은 "그렇다면 r이 주어져 있을 때 과연 n은 무엇인지 알 수 있나?"라는 문제를 제시한다. 이렇게 해서 나오게 된 것이 Ramsey number R(r)이다. 그런데 이게 참 tricky한게, 저 R(n)을 찾는 것이 정말 어렵단다. 지금까지 알려진 것은 다음과 같다.

Erdos라고 엄청 유명한 수학자가 Ramsey number가 얼마나 찾기가 힘든지 이런 얘기를 다 했다.

Aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five [that is, R(5,5)]. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.

외계인이 쳐들어 와서 R(5)를 찾아내라고 하면 1년 동안 세상에서 제일 똑똑한 사람들과 제일 빠른 컴퓨터들을 동원해서 찾을 수 있겠지만, R(6)를 찾으라고 하면 죽었다 생각하고 먼저 공격해버리는 수 밖에 없다는 것이다.

engineered.egloos.com/2136980