개념
"n+1마리 비둘기를 n개 둥지에 넣으면 적어도 한 둥지에 두 마리가 들어간다." 자명해 보여도 유한 그래프 색칠, 램지 이론, 디리클레 근사의 핵심 도구.
한 호흡으로 이해하기
"서울 시민 1000만 명 중 머리카락 수가 정확히 같은 두 사람이 반드시 있다." (사람 머리카락 < 100만 가닥). 한 줄 원리가 국제수학올림피아드의 단골 무기이고, 램지 이론("어떤 큰 패턴이라도 더 큰 구조 안에 반드시 있다")의 출발점.
한눈에 보기
상황 | 비둘기집 | 비둘기 | 결론 |
|---|---|---|---|
1년에 367명 모임 | 366일 | 367명 | 같은 생일이 있다 |
서울 시민 1000만 | 머리카락 수 < 100만 | 1000만 | 머리카락 수 정확히 같은 두 사람 |
8 카드 손에 5장 | 4가지 무늬 | 5장 | 같은 무늬 적어도 2장 |
n+1마리 비둘기 | n개의 둥지 | n+1 | 어떤 둥지에 ≥ 2마리 |
압축 알고리즘 | 출력 길이 < 입력 가능 수 | 입력 모음 | 손실 없는 일반 압축은 불가능 |
"많이 보이지 않는 원리가 가장 강력한 도구가 된다" — 디리클레가 무리수 근사에 처음 사용. 램지 이론의 출발점.
핵심 식
|A| > |B| ⟹ 단사 함수 없음
오늘날의 응용
해시 충돌 보장, 압축 한계 증명, 알고리즘 하한.
MathVoyage 너머로
불러오는 중…