비둘기집 원리

➤ 비둘기집 원리

Pigeonhole Principle, PHP

비둘기

kn+1

마리와 비둘기집

n

개가 있으면 적어도 한 집에는 비둘기가

k+1

마리 이상 들어가 있다는 원리이다.

목차

1. 증명
2. 예시
2.1. 문제
2.2. 증명
3. 일반화
4. 영상

1. 증명 _{✎ ⊖}

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

2. 예시 _{✎ ⊖}

2.1. 문제 _{✎ ⊖}

한 변의 길이가 3인 정사각형 내부에 10개의 점이 선택되었다. 이들 중 두 점 사이의 거리가

\sqrt2

이하인 두 점이 존재함을 보여라.

2.2. 증명 _{✎ ⊖}

자명하다.⁽¹⁾

먼저 변의 길이가 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$ 마리 이상의 비둘기가 있다.

4. 영상 _{✎ ⊖}

이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.

(1) 농담입니다.

1. 증명 ✎ ⊖

2. 예시 ✎ ⊖

2.1. 문제 ✎ ⊖

2.2. 증명 ✎ ⊖

3. 일반화 ✎ ⊖

4. 영상 ✎ ⊖