비둘기집 원리
비둘기집에 비둘기가 더 많으면
서랍 속에 검은 양말 10켤레와 흰 양말 10켤레가 마구 섞여 있습니다. 방에 불이 꺼져 캄캄합니다.
양말을 최소한 몇 짝 꺼내야 같은 색깔 양말 한 켤레(2짝)를 확실하게 맞출 수 있을까요? 단 3짝만 집어 들면 무조건 짝이 맞는 마법 같은 수학 원리는 무엇일까요?
이야기
Unknown authorUnknown author
Public domain · 위키미디어 공용
서랍이 세 개인데 양말이 네 켤레 있습니다. 그러면 어떤 서랍에는 반드시 둘 이상 들어갑니다. 너무 당연해서 이것이 정리라는 것이 이상할 정도입니다.
그런데 이 당연한 말이 놀라운 것을 증명합니다.
서울에 머리카락 수가 똑같은 두 사람이 반드시 있을까요? 있습니다. 사람 머리카락은 많아야 십오만 올쯤입니다. 서울 인구는 구백만이 넘습니다. 서랍이 십오만 개인데 양말이 구백만 켤레인 셈입니다.
또 있습니다. 아무 사람이나 367명을 모으면 생일이 같은 두 사람이 반드시 있습니다. 날짜는 366개뿐이니까요.
이 원리의 힘은 누구인지 몰라도 있다고 말할 수 있다는 데 있습니다. 서울에서 머리카락 수가 같은 두 사람이 누구인지는 아무도 모릅니다. 그런데 있습니다.
수학에는 이렇게 「찾지 않고 증명하는」 방법들이 있습니다.
이 원리가 힘을 갖는 까닭은 어느 칸인지 몰라도 되기 때문입니다. 「어딘가 둘이 든 칸이 있다」만 말하고 그것이 어디인지는 말하지 않습니다. 그런데도 결론은 확실합니다.
이 원리에 「서랍 원리」라는 이름을 붙인 사람은 디리클레입니다. 1834년의 일입니다. 너무 뻔해 보이는 이 한 줄로 그는 수론의 어려운 정리들을 증명했습니다.
파일 압축의 한계를 정합니다. 「모든 파일을 줄여 주는 압축 프로그램」은 만들 수 없습니다 — 줄인 결과가 원본보다 가짓수가 적으니 반드시 둘이 겹치고, 겹치면 되돌릴 수 없기 때문입니다.
해시 충돌이 반드시 있다는 것도 같은 이유입니다.
계단 넷 — 같은 사실을 네 깊이로
양말·사탕으로 해 본다
비둘기집 3개에 비둘기 4마리가 들어간다고 상상해 보세요. 아무리 골고루 나누어 들어가려 해도, 어느 한 집에는 반드시 2마리 이상이 들어갈 수밖에 없습니다.
양말 색깔이 2종류(검정, 흰색)뿐이므로 3짝을 꺼내면 무조건 같은 색이 2짝 이상 생깁니다. 너무나 당연해 보이는 이 생각이 놀라운 수학의 열쇠입니다.
양말을 몇 개 꺼내야 할까요
「운이 좋으면 2 개」와 「확실하려면 k+1 개」는 다른 물음입니다.
머리카락 수·생일로 논증
이 당연한 사실을 수학에서는 비둘기집 원리(Pigeonhole principle) 또는 디리클레의 상자 원리라고 부릅니다.
사람의 머리카락 수는 보통 10만 가닥 안팎입니다. 서울 시민(약 900만 명) 중에는 머리카락 수가 완전히 똑같은 사람이 적어도 수십 명 이상 반드시 존재합니다. 일일이 세어보지 않고도 100% 확신할 수 있는 강력한 논증입니다.
같은 칸에 몇 개나
서울 사람 중 머리카락 수가 같은 사람이 반드시 있습니다 (머리카락은 15만 올 안쪽).
일반화된 비둘기집·에르되시 문제
일반화된 비둘기집 원리에 따르면, 개의 상자에 개의 물건을 넣으면 적어도 한 상자에는 개 이상의 물건이 들어갑니다.
이를 정수론에 적용하면 임의의 무리수 에 대해 을 만족하는 유리수 근사가 무한히 존재한다는 디리클레의 디오판토스 근사 정리가 우아하게 증명됩니다.
두 수의 차가 나뉩니다
비둘기집은 「있다」만 말하고 「어디」는 말하지 않습니다.
램지 이론의 씨앗
비둘기집 원리는 극도로 거대한 조합적 구조 속에서 필연적으로 질서가 나타남을 보이는 램지 이론(Ramsey theory)의 씨앗입니다.
“완전한 무질서는 불가능하다”는 모토 아래, 6명이 모인 파티에서 서로 아는 3명이 존재하거나 서로 모르는 3명이 반드시 존재한다는 정리부터 에르되시-세케레스 정리에 이르기까지 현대 극단 조합론의 핵심 기둥입니다.
에르되시–세케레시
혼돈 속에도 반드시 질서가 있다 — 램지 이론의 시작입니다.
풀어 보기
비둘기집 원리의 응용. 다음 물음에 답하시오.
(1) 1년(365일) 중 생일이 같은 사람이 반드시 존재하도록 하려면 최소 몇 명이 모여야 하는지 구하시오.
(2) 한 변의 길이가 1인 정사각형 안에 점 5개를 무작위로 찍었다. 이 중 두 점 사이의 거리가 이하인 두 점이 반드시 존재함을 증명하시오.
(3) 1부터 20까지의 자연수 중 서로 다른 11개의 수를 고를 때, 두 수의 합이 21이 되는 두 수의 쌍이 반드시 존재함을 보이시오.
(2) 는 정사각형을 4개의 작은 정사각형()으로 분할해 보세요.
답과 풀이 보기
(1) 366 명입니다.
365 명까지는 모두 다른 날일 수 있습니다. 366 번째 사람은 어느 날에 서든 이미 누가 서 있습니다.
(윤년까지 셈에 넣으면 367 명입니다.)
(2) 정사각형을 인 작은 정사각형 네 개로 나눕니다.
점이 다섯 개이므로 비둘기집 원리에 따라 어느 한 칸에 두 점이 들어갑니다.
한 칸 안에서 가장 먼 두 점은 대각선 양 끝이고 그 길이는
그러므로 그 두 점의 거리는 이하입니다.
(3) 합이 21 이 되는 짝을 미리 묶어 놓습니다.
— 10 쌍입니다.
이 열 쌍이 1 부터 20 까지를 남김없이 덮습니다.
열한 개를 고르면 비둘기집 원리에 따라 어느 한 쌍에서 둘 다 고르게 되고, 그 두 수의 합이 21 입니다.
⭐ 열 개까지는 피할 수 있습니다 — 쌍마다 하나씩만 고르면 됩니다.
비둘기집 원리는 「집보다 비둘기가 많으면 겹친다」는 당연한 말입니다.
그런데 무엇을 집으로 삼을지를 잘 고르면 증명하기 어려워 보이던 것이 한 줄로 끝납니다. (2) 에서 네 칸으로 나눈 것이 그 전부였습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
비둘기집 원리는 어려운 증명의 밑돌입니다.
- 램지 이론 — 파티 문제가 이 원리에서 자랐습니다
- 압축의 한계 — 모든 파일을 줄이는 압축 방법은 있을 수 없습니다. 서랍이 모자라기 때문입니다
- 해시 충돌 — 서로 다른 자료가 같은 값을 갖는 일은 반드시 생깁니다
이어지는 장
여섯 명만 모여도 서로 알거나 모르는 세 사람이 반드시 존재한다는 파티 문제의 명쾌한 해답 뒤에는 바로 이 단순하고도 강력한 서랍의 원리가 숨어 있습니다 — 제71장 에서 비둘기집 원리가 어떻게 쓰이는지 확인해 보세요.
영감을 받은 곳
페터 구스타프 르죈 디리클레(Peter Gustav Lejeune Dirichlet)가 1834년 논문에서 수론의 문제를 풀기 위해 '서랍 원리(Schubfachprinzip)'라는 이름으로 공식화한 논증 원리에서 왔습니다.