비둘기집의 원리

누리위키, 온 누리의 백과사전
ProtArie (토론 | 기여)님의 2013년 8월 29일 (목) 14:53 판 (새 문서: '''비둘기집의 원리'''(The pigeonhole principle)이란 \(n+1\) 마리 이상의 비둘기를 \(n\)개의 집에 넣으려고 할 때, 적어도 하나의 집에는 두 마...)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)

비둘기집의 원리(The pigeonhole principle)이란 \(n+1\) 마리 이상의 비둘기를 \(n\)개의 집에 넣으려고 할 때, 적어도 하나의 집에는 두 마리 이상의 비둘기가 들어가게 된다는 정리이다. 디리클레의 방 나누기 원리라고도 한다.

증명[편집]

귀류법을 사용하여 증명한다. \(n\)개의 집과 \(n+1\)마리 이상의 비둘기가 있다고 가정하자. 그리고 각각의 집에는 한 마리 이하의 비둘기만 들어 있다고 가정하자. 그러면 집에 들어가 있는 비둘기의 수는 많아야 \(n\)마리 일 것이므로, \(n+1\)마리 이상의 비둘기가 있다는 것은 모순이다.

일반화된 정리[편집]

\(n\)개의 물건을 \(m\)개의 상자에 넣으면, 적어도 한 개의 상자에는 \( \displaystyle{ \left\lceil \frac{n}{m} \right\rceil } \)개 이상의 물건이 들어가 있다. 여기서 \(\lceil x\rceil \)는 x의 올림(round-up)이다.