Q 어떤 모임에 정치인 6명이 참석했다. 이들은 그다지 사이가 좋은 편이 아니어서, 어떤 3명을 골라도 그 가운데 그날 서로 악수하지 않은 정치인이 적어도 한 쌍은 있었다. 그렇다면 이들 가운데 서로 한 번도 악수하지 않은 정치인 3명을 찾을 수 있을까?
A 이해하기 쉽게 그림으로 바꿔 생각해 보자. 정치인 6명 대신 평면에 점 6개를 표시한 다음 각 점을 실선과 점선으로 연결하자. 서로 악수한 경우를 실선으로, 악수하지 않은 경우를 점선으로 그린다고 하자.
세 점 A, B, C를 아무렇게나 고른다. 만약 이 세 점이 점선으로 연결된 삼각형을 이룬다면 문제에서 요구하는 정치인 3명을 찾은 것이다. 이 세 점이 이루는 삼각형의 세 변 가운데 AC만 실선이라고 가정해 보자. 나머지 세 점 D, E, F에 대해 마찬가지로 생각해서 DF가 실선이라고 하자(01).
만약 AF가 실선이라면 AD, CF는 점선이라야 한다(02). BD가 점선이라면 ABD가 점선 삼각형이 되고, BD가 실선이라면 BCF가 점선 삼각형이 된다. CD가 실선인 경우도 마찬가지이다. 만약 AF와 CD가 모두 점선이라면, 삼각형 ABF나 삼각형 BCD가 점선 삼각형이 된다(03).
삼각형 ABC에서 한 변 AB만 점선인 경우를 생각해 보자. 앞서와 마찬가지로 DF가 실선이라고 하자. CD가 실선이면 AD가 점선이라야 한다. 또 BD도 점선이라야 하니까 ABD가 점선 삼각형이 된다. AF, CD 모두 점선일 때는 삼각형 ABF가 점선 삼각형이 되거나 BF가 실선이 돼야 한다. BF가 실선이라면 삼각형 ABF가 한 변만 실선인 삼각형이 되는데 이것은 우리가 가장 먼저 고려했던 경우다. 마지막으로 AF가 실선인 경우가 남는데, 이 경우는 독자 여러분들이 직접 해 보시라.
정치인이 5명이라면 서로 악수하지 않은 세 사람이 존재하지 않을 수도 있지만, 6명 이상이면 이런 일은 항상 가능하다. 바꿔 말하면, 서로 악수한 3명이 존재하거나, 서로 악수하지 않은 3명이 반드시 존재하려면 적어도 정치인 6명이 모여야 한다.
이 사실을 기호로 R(3, 3)=6으로 나타내고, 영국의 수학자이자 철학자, 경제학자였던 프랭크 플럼턴 램지의 이름을 따 ‘램지 수’라고 부른다. 만약 서로 악수한 4명이 존재하거나, 서로 한 번도 악수하지 않은 4명이 존재하려면 적어도 18명이 필요하다. 즉 R(4, 4)=18이다. 일반적인 경우의 램지 수를 구하는 것은 대단히 어려운 일이어서 R(5, 5)나 R(6, 6)의 경우에는 범위만이 알려져 있을 뿐이다.
지난달 정답_ 3개
