비둘기집 원리

1 개요

pigeonhole principle, Dirichlet's box principle, Dirichlet's drawer principle

비둘기집 원리, 디리클레의 상자 원리, 디리클레의 서랍 원리

• n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 2개 이상의 물건이 들어 있다는 원리

 

2 일반화

• [math]\displaystyle{ n }[/math]개의 별개의 사물을 [math]\displaystyle{ m }[/math]개의 용기에 나누어 담으면 적어도 한 개의 용기는 [math]\displaystyle{ \left\lceil \frac n m \right\rceil }[/math] 이상의 사물을 담고 있어야 한다.

3 같이 보기

• 샌드위치 정리
• 램지의 정리
• 해시 충돌

4 참고

• https://ko.wikipedia.org/wiki/비둘기집_원리