모던지 / 수학 / 이산수학 4강. 비둘기집 원리와 램지 이론

이산수학 4강. 비둘기집 원리와 램지 이론

비둘기 10마리를 상자 9개에 넣으면 어딘가는 두 마리입니다. 이 뻔한 문장이, 완전한 무질서는 불가능하다는 심오한 결론까지 끌고 갑니다.

풀고 시작

문제 1. 서울에 머리카락 개수가 정확히 같은 두 사람이 반드시 존재한다고 증명할 수 있을까요?

사람의 머리카락은 많아야 15만 개 안팎이므로 가능한 개수의 가짓수는 15만 남짓인데, 서울 인구는 900만이 넘습니다. 상자보다 비둘기가 많으면 어떤 상자엔 둘 이상이 들어간다는 비둘기집 원리에 의해, 단 한 명도 조사하지 않고 존재를 확언할 수 있죠.

비둘기집 원리: 뻔함의 힘

비둘기집 원리(pigeonhole principle)의 진술은 싱겁습니다. 비둘기가 n마리, 집이 m개이고 n > m이면, 적어도 한 집에는 두 마리 이상이 들어갑니다. 19세기 수학자 디리클레가 정수론 증명에 체계적으로 사용해 "디리클레의 서랍 원리"라고도 불리죠. 증명은 대우 한 줄입니다. 모든 집에 한 마리 이하라면 비둘기는 많아야 m마리인데, 이는 n > m과 모순입니다.

그런데 이 싱거운 원리가 강력해지는 순간이 있습니다. "무엇이 비둘기이고 무엇이 집인가"를 발명할 때입니다. 서울 시민이 비둘기, 머리카락 개수(0개부터 15만 개 남짓)가 집이라고 보면, 900만이 넘는 인구가 15만 개 남짓한 집에 들어가므로 같은 개수의 두 사람이 반드시 존재합니다. 실제로는 평균적으로 수십 명이 같죠. 마찬가지로 366명이 모이면 생일이 같은 두 사람이 확실히 존재하고(1강의 생일 역설이 23명에서 "확률 절반"이었다면 여기는 "확실성"입니다), 13명이 모이면 같은 달에 태어난 두 사람이 반드시 있습니다. 주목할 점은 이 원리가 누구인지 전혀 알려 주지 않으면서 존재만 보증한다는 것입니다. 대상을 하나도 조사하지 않고 존재를 증명하는 비구성적 논법의 가장 순수한 형태죠.

파티 문제: R(3,3) = 6

이제 원리를 한 단계 밀어붙여 봅시다. 파티에 몇 명이 모이면, 서로 전부 아는 3명 또는 서로 전부 모르는 3명이 반드시 생길까요. 답은 6명이고, 논증은 다음과 같습니다.

6명 중 아무나 한 사람 A를 잡습니다. A와 나머지 5명의 관계는 "안다" 또는 "모른다" 둘 중 하나이므로, 비둘기집 원리에 의해 적어도 3명과는 같은 관계입니다. A가 B, C, D를 안다고 합시다(모르는 경우도 대칭으로 같습니다). 이제 B, C, D 사이를 보시죠. 그중 어느 두 사람이라도 서로 알면, 그 둘과 A가 서로 아는 3명입니다. 반대로 셋 중 누구도 서로 모르면, B, C, D 자신이 서로 모르는 3명이죠. 어느 쪽이든 결론이 나옵니다. 한편 5명으로는 부족합니다. 다섯 명을 원형으로 세워 이웃끼리만 아는 사이로 만들면, 서로 아는 3명도 서로 모르는 3명도 생기지 않는 반례가 되거든요. 그래서 이 문제의 답, 즉 램지 수 R(3,3)은 정확히 6입니다.

램지 이론: 완전한 무질서는 불가능하다

이 파티 문제를 일반화한 것이 램지 이론(Ramsey theory)입니다. 영국의 천재 프랭크 램지가 1930년 논리학 논문에서 증명한 정리가 출발점인데, 그는 그해 26세로 요절했습니다(철학, 경제학에도 발자국을 남긴 인물로, 케인스와 비트겐슈타인의 동료였죠). 램지 정리의 요지는 이렇습니다. 충분히 큰 구조는, 아무리 무작위로 칠해도, 반드시 질서 있는 부분을 품는다. 수학자 모츠킨은 이를 "완전한 무질서는 불가능하다"라는 문장으로 요약했습니다. 무질서는 규모를 이길 수 없다는 것이죠.

그러나 "충분히 큰"이 얼마인지 아는 것은 전혀 다른 문제입니다. R(4,4) = 18까지는 알지만, R(5,5)는 오랫동안 43 이상 48 이하라는 범위 정도만 알려져 있을 뿐 정확한 값을 아직 모릅니다. 경우의 수가 조합 폭발(1강)로 자라기 때문이죠. 에르되시의 유명한 비유가 있습니다. 외계인이 R(5,5)를 내놓지 않으면 지구를 파괴하겠다고 하면 전 인류의 컴퓨터와 수학자를 총동원해 계산을 시도해야 하지만, R(6,6)을 요구한다면 차라리 외계인을 없앨 방법을 찾는 편이 낫다는 것입니다.

에르되시와 조합론 문화

헝가리 출신의 에르되시(1913~1996)는 집도 직장도 없이 가방 하나로 전 세계 동료의 집을 떠돌며 "내 두뇌는 열려 있다"라는 인사와 함께 공동 연구를 한 방랑 수학자입니다. 평생 약 1,500편의 논문을 500명이 넘는 공저자와 썼고, 그와의 공저 거리를 나타내는 "에르되시 수"는 수학계의 유명한 놀이가 됐죠(2강의 좁은 세상 네트워크가 수학자 사회 안에서 실증되는 셈입니다). 그는 좋은 미해결 문제에 현상금을 거는 전통을 만들었고, 확률적 방법이라는 강력한 기법으로 램지 수의 하한을 증명해 조합론을 현대 수학의 중심 분야로 끌어올렸습니다. 신이 가장 아름다운 증명만 모아 둔 "그 책(The Book)"이 있다는 그의 농담은, 증명에도 아름다움의 위계가 있다는 조합론 문화의 자기 이해를 잘 보여 줍니다. 다음 과목인 선형대수에서는 이산적인 세기에서 연속적인 공간의 수학으로 자리를 옮깁니다.

인출 문제

문제 1. 비둘기집 원리에 기반한 존재 증명의 특징은?

상자보다 비둘기가 많다는 개수 비교만으로 결론이 나오므로, 조사 없이도 존재가 논리적으로 확정됩니다. 다만 그 두 사람이 누구인지는 전혀 알려 주지 않죠. 확률적 주장(1강의 생일 역설)과 달리 이것은 100%의 확실성이라는 점이 핵심 차이입니다.

문제 2. R(3,3) = 6 논증에서 비둘기집 원리가 쓰이는 지점은?

5명을 "안다"와 "모른다"라는 두 상자에 넣으면 한 상자에 3명 이상이 들어간다는 것이 논증의 첫걸음입니다. 그다음 그 3명 사이의 관계를 경우로 나누면 어느 쪽이든 질서 있는 3인조가 나오죠. 원형 배치 반례는 5명으로는 부족함을 보이는 별도 단계입니다.

문제 3. "완전한 무질서는 불가능하다"라는 문장이 요약하는 램지 이론의 통찰은?

램지 정리는 구조가 일정 규모를 넘으면 어떤 칠하기에서도 단색의 부분 구조가 강제됨을 보입니다. 무질서가 불가능하다는 말이 아니라, 규모가 커지면 무질서가 국소적 질서의 출현을 막을 수 없다는 뜻이죠.

문제 4. 에르되시의 외계인 비유에서 R(5,5)와 R(6,6)의 차이가 말해 주는 것은?

R(5,5)는 인류의 전 자원을 쏟으면 혹시 구할 수도 있지만 R(6,6)은 그런 희망조차 없다는 비유입니다. 확인해야 할 그래프의 수가 조합 폭발로 자라기 때문이며, 존재 자체는 램지 정리가 보증하므로 값이 없는 것이 아니라 값을 모르는 것입니다.

생각해볼 질문 (정답 없음)

별자리는 별들의 무작위 배치에서 인간이 읽어 낸 패턴입니다. 램지 이론의 관점에서, 우리가 세계에서 발견하는 "의미 있는 패턴" 중 얼마나 많은 것이 단지 규모가 큰 무작위의 필연적 부산물일까요.

이전: 3강 수학적 귀납법과 재귀 · 다음: 선형대수 1강

이 문서를 언급함

← 이산수학 3강. 수학적 귀납법과 재귀 ← 선형대수 1강. 벡터와 벡터공간 ← 수학

모던지 · 궁금하면 모던지 GitHub · 2026-09-10