비둘기집 원리

n+1개의 물건을 n개의 상자에 넣으면, 최소 한 상자에는 물건이 2개 이상 들어간다.
존재성을 증명하지만, 특정 대상을 찾아주지는 않는 비건설적 증명의 대표적인 예시다.
프로그래밍에선 해시 테이블 에 충돌이 발생할 수 밖에 없는 원리
구성 요소
- 비둘기 (Pigeons): 문제에서 고려해야 할 대상들의 집합
- 비둘기집 (Pigeonholes): 대상들이 속하게 될 카테고리나 공간의 집합
핵심 조건: 비둘기의 수 > 비둘기집의 수
결론: 최소한 하나의 비둘기집에는 2마리 이상의 비둘기가 존재한다.
예시: 13명의 사람이 있다면, 같은 달에 태어난 사람이 최소 2명은 반드시 존재한다.
- 비둘기: 13명의 사람
- 비둘기집: 12개의 달 (1월, 2월, …, 12월)
- 결론: 비둘기(13)가 비둘기집(12)보다 많으므로, 어떤 달에는 최소 2명의 생일이 포함된다.

시스매