비둘기집의 원리 ➤ 비둘기집 원리
(+)분류 : 가져온 문서/오메가
Pigeonhole Principle, PHP
비둘기 kn+1마리와 비둘기집 n개가 있으면 적어도 한 집에는 비둘기가 k+1마리 이상 들어가 있다는 원리이다.
1. 증명 ✎ ⊖
직관적으로도 자명하고, 간단히 귀류법을 이용해 증명할 수 있다.
2. 예시 ✎ ⊖
2.1. 문제 ✎ ⊖
한 변의 길이가 3인 정사각형 내부에 10개의 점이 선택되었다. 이들 중 두 점 사이의 거리가 \\sqrt2 이하인 두 점이 존재함을 보여라.
2.2. 증명 ✎ ⊖
자명하다.(1)
먼저 변의 길이가 3인 정사각형을 변의 길이가 1인 정사각형 9개로 나누어보자.
여기서 점을 비둘기, 정사각형을 상자라 하면 어느 한 정사각형엔 두 개 이상의 점이 들어가고, 그 두 점 사이의 거리는 많아봐야 \\sqrt2인 것이다. ■
먼저 변의 길이가 3인 정사각형을 변의 길이가 1인 정사각형 9개로 나누어보자.
여기서 점을 비둘기, 정사각형을 상자라 하면 어느 한 정사각형엔 두 개 이상의 점이 들어가고, 그 두 점 사이의 거리는 많아봐야 \\sqrt2인 것이다. ■
3. 일반화 ✎ ⊖
일반화된 비둘기집 원리(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마리 이상의 비둘기가 있다.
