비둘기집 원리 (원본) (1)

[[분류:가져온 문서/오메가]]
Pigeonhole Principle, PHP

비둘기 [math(kn+1)]마리와 비둘기집 [math(n)]개가 있으면 적어도 한 집에는 비둘기가 [math(k+1)]마리 이상 들어가 있다는 원리이다.

== 증명 ==
직관적으로도 자명하고, 간단히 귀류법을 이용해 증명할 수 있다.

== 예시 ==
=== 문제 ===
한 변의 길이가 3인 정사각형 내부에 10개의 점이 선택되었다. 이들 중 두 점 사이의 거리가 [math(\sqrt2)] 이하인 두 점이 존재함을 보여라.

=== 증명 ===
자명하다.[* 농담입니다.]

먼저 변의 길이가 3인 정사각형을 변의 길이가 1인 정사각형 9개로 나누어보자.

여기서 점을 비둘기, 정사각형을 상자라 하면 어느 한 정사각형엔 두 개 이상의 점이 들어가고, 그 두 점 사이의 거리는 많아봐야 [math(\sqrt2)]인 것이다. ■

== 일반화 ==
일반화된 비둘기집 원리(Generalized Pigeonhole Principle)

>[math(1\leq i \leq n)]일 때, [math(n, k_i\in \mathbb{N})]에 대해 만약 [math(\displaystyle\sum_{i=1}^n k_i -n+1)]개 이상의 비둘기를 [math(n)]개의 비둘기 집에 넣었다면, 어떤 [math(i)]가 존재하여 [math(i)]번째 집에 [math(k_i)]마리 이상의 비둘기가 있다.

== 영상 ==
[youtube(RiknxHRe24w)]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]