파티 문제
여섯 명만 모이면 셋은 통합니다
파티에 모인 6명의 사람 중 아무나 두 사람을 짝지어 서로 아는 사이면 파란 선, 모르는 사이면 빨간 선으로 이어 보세요.
어떻게 인간관계를 얽어 놓아도 서로 모두 아는 3명이 생기거나, 서로 전혀 모르는 3명이 반드시 생겨납니다. 무질서해 보이는 만남 속에서 어떻게 완벽한 질서가 필연적으로 피어날까요?
이야기
Volsav
CC BY-SA 4.0 · 위키미디어 공용
1928년 케임브리지. 스물다섯 살의 프랭크 램지가 논리학 논문 하나를 씁니다. 「어떤 문제가 기계적으로 풀리는가」를 따지던 글이었고, 이 정리는 그 안의 보조 도구였습니다. 파티 이야기는 어디에도 없었습니다.
램지는 그 논문이 실리기도 전인 스물여섯에 세상을 떠났습니다. 황달 수술을 받다가였습니다.
그런데 이 정리에는 아직 아무도 답을 모르는 자리가 있습니다. 여섯 명이면 세 사람이 나온다는 것은 쉽습니다. 네 사람이 나오려면 열여덟 명이 필요하다는 것까지도 밝혀졌습니다. 그러나 다섯 사람이 나오려면 몇 명이 필요한지는 지금도 모릅니다. 43명에서 46명 사이라는 것까지가 전부입니다.
왜 여섯이면 되는지는 비둘기집으로 보입니다. 한 사람을 세워 놓고 나머지 다섯과의 관계를 보십시오. 「안다」와 「모른다」 두 칸에 다섯을 나누어 담으면 한 칸에는 반드시 셋 이상이 들어갑니다.
그 셋이 모두 「아는」 사이라 합시다. 셋 가운데 서로 아는 짝이 하나라도 있으면 그 둘과 처음 사람이 서로 다 아는 세 사람이 됩니다. 하나도 없다면 그 셋이 서로 다 모르는 세 사람입니다. 어느 쪽이든 피할 길이 없습니다.
어느 쪽이든 피할 길이 없는 것은 다섯을 두 칸에 나눠 담으면 반드시 한 칸이 셋 이상이 되기 때문입니다. 사람이 몇 명이든, 관계가 어떻게 얽혔든 이 셈은 무너지지 않습니다.
「아무리 어지럽혀도 질서가 남는다」는 것을 보입니다. 여섯 명이면 서로 아는 셋이나 모르는 셋이 반드시 있습니다.
통신망 설계에서 「어떤 고장이 나도 남아 있는 연결」을 보장하는 데 같은 이론이 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
점 여섯에 두 색으로 선을 그어 본다
원 위에 점 6개를 찍고 한 점을 '나'라고 합시다. 나와 다른 5명 사이에는 파란 선(친구) 또는 빨간 선(남) 5개가 그어집니다.
선이 5개이니 같은 색의 선이 적어도 3개는 있을 수밖에 없습니다. 그 3명의 친구들 사이를 선으로 이어 보며 파란 삼각형이나 빨간 삼각형이 무조건 만들어지는 것을 직접 눈으로 확인해 보세요.
여섯 명이면 반드시 있습니다
그 셋 사이를 보면 반드시 서로 아는 셋이나 모르는 셋이 나옵니다.
비둘기집으로 논증
나에게 연결된 같은 색(예: 파란색)의 선 3개가 연결된 사람들을 A, B, C라 합시다.
만약 A, B, C 셋 중 두 사람이라도 서로 파란 선으로 이어진다면 나와 함께 '서로 아는 3명'이 완성됩니다. 만약 셋 사이에 파란 선이 하나도 없다면 A, B, C 셋이 모두 빨간 선으로 이어져 '서로 모르는 3명'이 됩니다. 어느 쪽이든 단색 삼각형이 반드시 생깁니다.
비둘기집으로 세어 보세요
그 셋이 서로 아는 사이면 끝, 아니면 그 사람과 함께 셋이 됩니다.
램지 수 R(3,3)=6 증명
이 정리는 램지 수(Ramsey Number) 의 증명입니다. 완전그래프 의 변을 2색으로 칠할 때 단색 이 반드시 존재함을 보인 것입니다.
5개의 점으로는 외곽에 오각형(파랑), 내부에 별(빨강)을 그리면 단색 삼각형이 없는 반례()가 존재하므로, 6은 조건을 만족하는 최소의 수임이 엄밀히 증명됩니다.
더 큰 무리를 찾으려면
R(5,5) 는 43 과 48 사이라는 것만 압니다 — 70 년째 그대로입니다.
램지 이론
영국의 천재 수학자 프랭크 램지가 1930년 제시한 램지 이론(Ramsey Theory)은 "완전한 무질서는 불가능하다"는 심오한 철학을 담고 있습니다.
시스템의 규모가 충분히 커지면 아무리 무작위로 흩뿌려도 그 안에 일정한 규칙과 질서를 품은 부분구조가 필연적으로 나타납니다. 오늘날 정보이론, 통신 네트워크의 노이즈 필터링, 에르고딕 이론의 기초가 됩니다.
에르되시의 외계인
R(6,6)을 대라 하면 외계인을 공격하는 편이 낫다.」
풀어 보기
6명의 파티와 선 그래프. 6개의 꼭짓점을 가진 완전그래프 의 모든 변을 파란색 또는 빨간색으로 칠한다.
(1) 한 꼭짓점에서 뻗어나가는 5개의 변 중 같은 색으로 칠해진 변은 적어도 몇 개 이상 존재하는가? (사용한 원리의 이름을 쓰시오)
(2) 꼭짓점이 5개일 때 단색 삼각형이 하나도 생기지 않도록 2색으로 칠하는 구체적인 그래프 구조를 설명하시오.
(3) 단색 삼각형이 반드시 존재함을 보장하는 최소의 꼭짓점 수 의 값을 쓰시오.
(1) 비둘기집 원리에 의해 개입니다. (2) 정오각형 둘레 파랑, 내부 별 빨강입니다.
답과 풀이 보기
(1) 3 개 이상입니다 — 비둘기집 원리입니다.
변 5 개를 색 2 가지에 나누어 담으면 어느 한 색에는 반드시 개가 몰립니다.
그 3 개가 닿는 세 사람끼리 한 변이라도 같은 색이면 그 순간 단색 삼각형이고, 세 변이 모두 다른 색이면 그 셋이 반대색 삼각형이 됩니다. 어느 쪽이든 생깁니다.
(2) 정오각형의 둘레는 파랑, 그 안의 별 모양(대각선 5 개)은 빨강으로 칠합니다.
둘레도 다섯 고리, 별도 다섯 고리라 어느 색도 세 점을 한꺼번에 잇지 못합니다.
그래서 에서는 단색 삼각형을 피할 수 있습니다.
(3) 입니다.
다섯 명까지는 피할 수 있고, 여섯 명부터는 절대 피할 수 없습니다.
파티에 여섯 명만 모이면 서로 다 아는 세 사람이나 서로 다 모르는 세 사람이 반드시 있습니다. 누구를 부르든 상관없습니다.
그런데 는 아직 아무도 모릅니다. 에르되시는 말했습니다 — 외계인이 쳐들어와 를 대라 하면 온 인류가 힘을 합쳐 구해야 하고, 을 대라 하면 싸우는 편이 낫다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「완전한 무질서는 불가능하다」는 것이 램지 이론입니다.
- R(5,5)는 아직 모릅니다 — 43에서 48 사이라는 것만 압니다
- 에르되시의 농담 — 외계인이 R(5,5)를 대라 하면 힘을 모아 계산하고, R(6,6)을 대라 하면 싸워야 한다고 했습니다
- 직접 해 보기 — 점 여섯 개에 두 색으로 선을 그어 보세요. 반드시 한 색 삼각형이 생깁니다
이어지는 장
어떤 모임이든 여섯 명만 모이면 서로 다 아는 세 사람이거나 서로 다 모르는 세 사람이 반드시 존재한다는 필연성은, 비둘기가 집보다 많으면 한 방에 둘이 들어간다는 제98장 의 논리가 거대한 무질서 속에서도 완전한 질서가 반드시 싹튼다는 램지 정리로 도약하는 현장입니다.
영감을 받은 곳
영국의 천재 수학자이자 철학자인 프랭크 램지(Frank P. Ramsey)가 1930년 런던 수학회 회보에 발표한 기념비적 논문 「형식 논리의 문제에 관하여」(On a Problem of Formal Logic)에서 기초를 놓은 램지 이론(Ramsey Theory)에서 왔습니다.