비둘기집 원리(비둘기집 원리, pigeonhole principle)는 조합론에서 사용되는 기본적인 논리 원리로, “만약 $n$개의 물건을 $m$개의 구분된 구멍에 넣는 경우, $n>m$이면 적어도 하나의 구멍에 두 개 이상의 물건이 들어가게 된다”는 내용을 담고 있다.
정의
- 일반형: $n$개의 대상이 $m$개의 구분된 구획(비둘기집)에 배치될 때, $n>m$이면 적어도 하나의 구획에 두 개 이상의 대상이 배치된다.
- 강화형: 정수 $k\ge1$에 대해, $n>(k-1)m$이면 적어도 하나의 구획에 $k$개 이상의 대상이 들어간다.
어원 및 번역
- 원래 “Dirichlet’s Box Principle”(디리클레의 상자 원리)이라고 불리던 개념을 한국어로 직역한 것이 “비둘기집 원리”이다. 비둘기집(pigeonhole)이라는 은유는 물건을 작은 구멍에 넣는 모습을 떠올리게 하며, 영어 표현 “pigeonhole”을 그대로 번역한 것이다.
역사
- 19세기 독일 수학자 페르디난트 빌헬름 폰 디리클레(Ferdinand Wilhelm Dirichlet)가 제시한 원리이며, 이후 combinatorial mathematics와 probability theory에서 널리 활용되었다. 한국에서는 20세기 후반부터 수학 교과서와 대학 강의에서 “비둘기집 원리”라는 용어로 정착하였다.
주요 활용 분야
- 조합론: 존재 증명, 최소/최대 문제 등에서 직접적인 증명 도구로 사용.
- 컴퓨터 과학: 알고리즘의 복잡도 분석, 데이터 구조에서 충돌 충돌 방지 논증 등.
- 확률론: 사건의 중복 발생을 보이는 데 활용.
- 다른 분야: 그래프 이론, 정보 이론, 수학 교육 등에서도 교육용 예제로 자주 등장.
예시
- 간단한 예: 13명의 사람을 12개의 달력 달에 배정하면, 반드시 같은 달에 생일이 같은 두 사람이 존재한다(생일 문제).
- 강화형 예: 25개의 구슬을 6개의 상자에 넣을 때, 적어도 하나의 상자에는 5개 이상의 구슬이 들어간다($n=25, m=6, k=5$가 만족).
참고 문헌 및 자료
- 한국수학회, 조합론 입문, 2005.
- 김동현 외, 알고리즘과 데이터 구조, 2012.
- 영어 원문: Dirichlet, G. L. “Principle of Boxes,” 19th century.
위 내용은 일반적인 수학·컴퓨터 과학 분야에서 인정받는 “비둘기집 원리”에 대한 객관적인 설명이다.
