Pigeonhole Principle, PHP
비둘기
kn+1마리와 비둘기집
n개가 있으면 적어도 한 집에는 비둘기가
k+1마리 이상 들어가 있다는 원리이다.
직관적으로도 자명하고, 간단히 귀류법을 이용해 증명할 수 있다.
한 변의 길이가 3인 정사각형 내부에 10개의 점이 선택되었다. 이들 중 두 점 사이의 거리가 \\sqrt2 이하인 두 점이 존재함을 보여라.
자명하다.
(1)먼저 변의 길이가 3인 정사각형을 변의 길이가 1인 정사각형 9개로 나누어보자.
여기서 점을 비둘기, 정사각형을 상자라 하면 어느 한 정사각형엔 두 개 이상의 점이 들어가고, 그 두 점 사이의 거리는 많아봐야
\\sqrt2인 것이다. ■
일반화된 비둘기집 원리(Generalized Pigeonhole Principle)
1\\leq i \\leq n일 때, n, k_i\\in \\mathbb{N}에 대해 만약 \\displaystyle\\sum_{i=1}^n k_i -n+1개 이상의 비둘기를 n개의 비둘기 집에 넣었다면, 어떤 i가 존재하여 i번째 집에 k_i마리 이상의 비둘기가 있다.
