Section 9.2 The Pigeonhole Principle
The pigeonhole principle is the basic observation that is you have \(n\text{,}\) and you have \(m\) pigeonholes, and you have more pigeons than pigeonholes (that is, \(n > m\)), then at least one hole must contain two or more pigeons.
Subsection 9.2.1 Pigeonhole Principle
Theorem 9.2.1.
Consider \(n\) objects placed into \(k\) boxes.
If \(n > k\text{,}\) then at least one box contains more than one object.
If \(n \lt k\text{,}\) then at least one box is empty.
Despite sounding very intuitively obvious and trivial, the pigeonhole principle can be used for important applications, as well as prove some results that are very subtle. The pigeonhole principle is an existence theorem, in that it only provides information that such a box (with multiple objects or no objects) exists, without providing any information about how to find this box. The pigeonhole principle was first stated formally by Peter Gustav Lejeune Dirichlet (1805-1859), German mathematician.
Proof.
By contradiction, suppose \(n > k\) objects are placed into \(k\) boxes, and each box contains at most one object. Then, the total number of objects, \(n\text{,}\) is equal to the sum of the objects in each of the \(k\) boxes. Then, the sum of the objects in the \(k\) boxes is at most \(k \cdot 1 = k\text{,}\) because there is at most one object in each box. This implies that \(n \leq k\text{,}\) which contradicts the assumption that \(n > k\text{.}\)
By contradiction, suppose \(n \lt k\) objects are placed into \(k\) boxes, and no box is empty, that is, every box has at least one object. Then, the number of objects \(n\) is equal to the sum of the objects in each of the \(k\) boxes, which is at least \(k \cdot 1 = k\text{,}\) because each box contains at least one object. Thus, \(n \geq k\text{,}\) contradicting the assumption that \(n \lt k\text{.}\)
Subsection 9.2.2 Basic Examples
Example 9.2.2.
In any group of 13 people, there are at least two people who were born in the same month.
Example 9.2.3.
Suppose that every person has no more than 500,000 strands of hair. Then, in a city of more than 500,000 people, there are at least two people that have the exact same number of strands of hair.
Example 9.2.4.
Consider a 70cm by 70cm square that is shot with 50 bullets. Show there are a pair of bulletholes that are closer than 15cm. Then, improve the upper bound. Divide up the square into 49 smaller 7cm by 7cm squares.
Example 9.2.5.
Given 38 even integers (or simply integers) less than 1000, prove that there are 2 of them whose difference is at most 26.
Example 9.2.6.
Prove that for any 5 points in an equilateral triangle of side length 2, there exists a pair of points whose distance is at most 1.
Divide the triangle into 4 equilateral triangles of side length 1.
Subsection 9.2.3 Formal Version
More formally, the pigeonhole principle can be stated in terms of sets and functions.
Theorem 9.2.7.
Let \(A, B\) be finite sets, \(f: A \rightarrow B\) be a function. If \(\abs{A} > \abs{B}\text{,}\) then \(f\) is not one-to-one, i.e. there exists an element in the co-domain \(B\) which has two elements in the domain \(A\) mapping to it.
Subsection 9.2.4 Generalized Pigeonhole Principle
Theorem 9.2.8.
Consider \(n\) objects being placed into \(k\) boxes. Then,
At least one box contains \(\ceil{\frac{n}{k}}\) or more objects.
At least one box contains \(\floor{\frac{n}{k}}\) or fewer objects.