램지 수(Ramsey Number) 퍼즐

 또다른 파티 문제이다.

 어떤 두 사람이건 서로 한 번은 만나보았거나(빨간 선), 혹은 단 한 번도 만난 적이 없을 것이다(파란 선). 그림 왼쪽은 아무나 6명을 모았을 때 일어날 수 있는 관계도 중 하나를 그린 것이다. 

 이런 상황에서, 파티에 사람들을 초대하여 서로 한 번은 만나본 사람들 3명(빨간 삼각형)이 생기거나, 혹은 서로 전혀 만나본 적 없는 사람들 3명(파란 삼각형)이 생기도록 하고싶다.(동시에 두 그룹이 생기지 않아도 좋다.) 최악의 경우까지 고려할 때 최소한 몇 명이 파티에 모여야 할까?

설명

 그 최소 인원은 6명이다.

우선 6명이 모이면 언제나 조건을 만족함을 증명하자.

 모인 사람들 중 한 명을 임의로 생각하면 그(철수)는 나머지 다섯 사람들 중 3명 이상과 만나보았거나 그렇지 않을 것이다.

 그가 만난 사람이 있는 3명 이상 경우를 살피자. 이름을 붙여서 철수가 영희, 영수, 영주를 만나보았다고 하자. 영희 영수 영주 중 서로 만나본 2사람이 있으면 철수를 중심으로 서로 만나본 3명의 사람들 모임이 생기게 된다. 반대로 영희 영수 영주 중 서로 만나본 2사람이 전혀 없으면 그 자리에서 영희 영수 영주가 서로 전혀 만난 적 없는 3명의 모임이 된다.

 철수가 3명 이상 만난 사람이 없으면 반대로 이것은 철수가 못 만나본 사람이 3명 이상 있다는 것을 의미한다. 이름을 붙여서 철수가 영희, 영수, 영주와 만난 적 없다고 하자. 앞의 원리에서 단어만 바꾸면(만난->못 만난, 못 만난->만난) 조건을 만족하는 3명을 언제나 찾을 수 있다.

 그러나 5명이 모이면 조건을 만족하지 못하는 경우가 생길 수 있다. 그 최악의 경우란 아래 그림과 같다.

  최악의 경우를 고려하면 최소한 6명 이상 초대해야하는데, 그 6명이 모이면 무조건 조건을 만족하는 3명이 생기므로 답은 6명이다.

 소개한 퍼즐은 램지의 정리(Ramsey's Theorem)의 한 경우이다. 램지의 정리란, 정점의 개수가 충분히 큰 완전그래프가 있으면 그것의 모든 변을 2가지 색으로 무작위로 색칠해도 언제나 r개의 정점을 갖는 빨간색 완전그래프가 있거나 s개의 정점을 갖는 파란색 완전그래프가 있다는 정리이다. 사람 얘기로 풀어 설명하면, 충분히 많은 사람들을 모으면 서로 만나본 r명의 사람들 모임이 생기거나 서로 못 만나본 s명의 사람들 모임이 생긴다는 것이다. 이 모여야하는 최소한의 인원 수를 램지수(Ramsey Number)라고 하고 R(r,s)로 표기한다. 그러면 앞선 퍼즐은 R(3,3)이 얼마냐고 묻는 문제가 된다.

 재밌는 것은 숫자 r과 s가 조금이라도 높아지면 정확한 램지수를 찾는 일이 대단히 어려워진다는 것이다. R(4, 4)=18이 알려져있지만, R(5, 5)는 43부터 49사이의 수라는 것까지만이 알려진 상황이다. 당연히 이보다 더 숫자가 높아지면 추축할 수 있는 램지수의 범위가 더 커지게된다.그리고 수학자들의 절망은 더 깊어진다. R(3,3)을 알아낸 사람들은 더욱 도전의식을 불태우고 싶다면 R(4, 4)가 18이라는 것을 증명하는 것은 어떨지?