PROOF 62
증명하라.
비둘기집 원리
유한집합 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
유한집합 S 의 각 원소에 상자 1, …, n 가운데 하나를 정하는 것을 배치라 한다. 상자 i 에 들어간 원소의 모임을 Bᵢ 라 한다.
증명.
(1)각 원소는 한 상자에 들어가므로 B₁ ∪ ⋯ ∪ Bₙ = S약속
(2)각 원소가 들어가는 상자는 하나뿐이므로 서로 다른 Bᵢ 는 배반이다.약속
(3)그러므로 B₁, …, Bₙ 은 S 의 분할이다.(1), (2)
∎
보조정리 L1
배치에서 모든 상자의 원소가 1 개 이하이면 |S| ≤ n 이다.
증명.
(1)모든 i 에 대하여 |Bᵢ| ≤ 1 이라 하자.가정
(2)|S| = |B₁| + ⋯ + |Bₙ|D1, A1
(3)|B₁| + ⋯ + |Bₙ| ≤ 1 + ⋯ + 1(1), A2
(4)1 을 n 번 더한 값은 n 이다.A3
(5)|S| ≤ n(2), (3), (4)
∎
정리 T1
원소의 개수가 n 보다 큰 유한집합을 n 개의 상자에 배치하면, 원소가 두 개 이상 든 상자가 있다.
증명.
(1)|S| > n 이라 하자.가정
(2)모든 상자의 원소가 1 개 이하라고 하자.가정
(3)|S| ≤ n(2), L1
(4)|S| ≤ n 이면 n < |S| 는 성립할 수 없다. 이는 (1) 에 모순이다.(1), (3), A4
(5)그러므로 모든 상자의 원소가 1 개 이하인 것은 아니다.(4), R
(6)|Bᵢ| ≤ 1 이 아닌 i 가 존재한다.(5), Q
(7)그 상자는 |Bᵢ| ≥ 2 이다.(6), A5
∎
따름정리 C1
원소가 n+1 개인 집합을 n 개의 상자에 배치하면, 원소가 두 개 이상 든 상자가 있다.
증명.
(1)n < n+1A6
(2)|S| = n+1 이므로 |S| > n(1), 가정
(3)원소가 두 개 이상 든 상자가 있다.(2), T1
∎
따름정리 C2
사람의 머리카락 수에 상한 m 이 있고 어떤 도시의 인구가 m+1 보다 크면, 그 도시에는 머리카락 수가 같은 두 사람이 있다.
증명.
(1)머리카락 수는 0 이상 m 이하의 정수라 하자.가정
(2)가능한 값은 0, 1, …, m 의 m+1 개다.(1)
(3)사람마다 그 사람의 머리카락 수를 정하는 것은 m+1 개의 상자에 대한 배치다.(2), D1
(4)인구가 m+1 보다 크다고 하자.가정
(5)두 사람 이상이 든 상자가 있다.(3), (4), T1
(6)한 상자의 사람들은 머리카락 수가 같다.(3), D1
(7)그러므로 머리카락 수가 같은 두 사람이 있다.(5), (6)
(8)이 결론은 (1) 과 (4) 아래에서만 성립한다. 상한 m 과 인구는 증명이 아니라 확인해야 할 수치다.(1), (4), (7)
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
이 증명은 어느 상자에 몇 개가 들었는지 한 번도 확인하지 않는다. 그 대신 무엇을 쓰는지 확인하라.