PROOF 62

Prove.

The pigeonhole principle

On finite sets.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

An assignment of one of the boxes 1, …, n to each element of a finite set S is called a placement. The collection of elements placed in box i is denoted Bᵢ.

Proof.

(1)Each element goes into some box, so B₁ ∪ ⋯ ∪ Bₙ = Sconvention

(2)Each element goes into only one box, so distinct Bᵢ are disjoint.convention

(3)Therefore B₁, …, Bₙ form a partition of S.(1), (2)

∎

Lemma L1

If in a placement every box holds at most one element, then |S| ≤ n.

Proof.

(1)Suppose |Bᵢ| ≤ 1 for every i.assumption

(2)|S| = |B₁| + ⋯ + |Bₙ|D1, A1

(3)|B₁| + ⋯ + |Bₙ| ≤ 1 + ⋯ + 1(1), A2

(4)The sum of 1 added n times is n.A3

(5)|S| ≤ n(2), (3), (4)

∎

Theorem T1

If a finite set with more than n elements is placed into n boxes, then some box holds at least two elements.

Proof.

(1)Suppose |S| > n.assumption

(2)Suppose every box holds at most one element.assumption

(3)|S| ≤ n(2), L1

(4)If |S| ≤ n, then n < |S| cannot hold. This contradicts (1).(1), (3), A4

(5)Therefore it is not the case that every box holds at most one element.(4), R

(6)There exists an i for which |Bᵢ| ≤ 1 fails.(5), Q

(7)For that box, |Bᵢ| ≥ 2.(6), A5

∎

Corollary C1

If a set with n+1 elements is placed into n boxes, then some box holds at least two elements.

Proof.

(1)n < n+1A6

(2)Since |S| = n+1, |S| > n(1), assumption

(3)Some box holds at least two elements.(2), T1

∎

Corollary C2

If there is an upper bound m on the number of hairs on a human head and the population of some city exceeds m+1, then that city contains two people with the same number of hairs.

Proof.

(1)Suppose the number of hairs is an integer between 0 and m inclusive.assumption

(2)The possible values are 0, 1, …, m, which is m+1 values.(1)

(3)Assigning to each person that person's number of hairs is a placement into m+1 boxes.(2), D1

(4)Suppose the population exceeds m+1.assumption

(5)Some box holds at least two people.(3), (4), T1

(6)The people in one box have the same number of hairs.(3), D1

(7)Therefore there are two people with the same number of hairs.(5), (6)

(8)This conclusion holds only under (1) and (4). The bound m and the population are not proved; they are figures to be verified.(1), (4), (7)

∎

Remark

Can A1 be removed from this proof?

This proof never once checks how many elements any particular box holds. Check what it uses instead.