위키득계정 ↗
과학

비둘기집 원리

비둘기집 원리과학
영문명
Pigeonhole principle
기본 조건
물건 수가 상자 수보다 많음
결론
어느 상자에는 둘 이상
일반화
N개를 k곳에 넣으면 어느 곳에는 ⌈N/k⌉개 이상
비둘기집 원리는 n개의 상자에 n개보다 많은 물건을 넣으면 적어도 한 상자에는 물건이 두 개 이상 들어간다는 원리다. 실제 상자가 없어도 대상을 여러 부류로 나누는 문제에 적용할 수 있다.

수를 비교하는 증명

모든 상자에 물건이 하나 이하라면 전체 물건 수는 상자 수 이하일 수밖에 없다. 그런데 물건이 상자보다 많다는 조건과 맞지 않으므로 어느 상자에는 둘 이상 있어야 한다.

분류에 적용하기

13명을 태어난 달에 따라 12개 부류로 나누면 적어도 두 명은 같은 달에 태어났다. 누가 같은 달인지는 이 원리만으로 정해지지 않는다. 존재를 보장하는 주장과 특정 대상을 찾아내는 일은 다르다.

더 많은 수를 넣기

10개를 3곳에 넣으면 어느 곳에는 적어도 4개가 있다. 모든 곳에 3개 이하라면 총합이 최대 9개이기 때문이다. 일반적으로 양의 정수 k에 대해 ⌈N/k⌉가 이런 하한이다.

조건의 한계

모든 상자에 두 개 이상 들어간다고 말하는 원리는 아니다. 또한 정확히 n개를 n개 상자에 넣을 때에는 각 상자에 하나씩 넣을 수 있으므로 기본 결론이 항상 성립하지 않는다. 물건과 부류의 수를 정확히 비교해야 한다.

관련 문서

경우의 수 / 집합 / 자연수 / 부등식 / 천장 함수 / 포함 배제 원리