Thinking Like a Mathematician

The Pigeonhole principle

The quintessential counting argument

Jørgen Veisdal
Aug 23, 2019 · 8 min read
Image for post
Image for post
The pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.

History

Infinite sets

For practical reasons let us illustrate the finite case by imagining a classroom with 100 seats. Filled with students, one can make an inference about the size of the set of students in relation to size of the set of seats. If seats are vacant, the set of seats is larger than the set of students. If no seats are vacant and some students are standing, the size of the set of students is larger than that of seats, and so on.- Excerpt, "The Nature of Infinity and Beyond" by Veisdal (2018)

Definition

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Figure 1. A: More pigeons than pigeonholes |n| > |f(n)|. B: Same number of pigeons as pigeonholes |n| = |f(n)|. C: More pigeonholes than pigeons |n| < |f(n)|
Proof of Pigeonhole Principle
Suppose that the total number of pigeons n are to be put in m number of pigeonholes and n > m. Assume that there are no pigeonholes with at least n/m pigeons, i.e. that each pigeonhole has less than n/m pigeons:
Number of pigeons in each pigeonhole < n/m
Number of pigeons < m × n/m
Number of pigeons < n
But given that the number of pigeons is strictly equal to n, we have obtained a contradiction to our assumption that each pigeonhole has less than n/m pigeons. Hence there exists at least one pigeonhole with at least n/m pigeons.

Applications

Example A — Common Properties in Large Groups

At any given time there live at least two people in California with the same number of hairs on their heads
Proof of Example A (Hammack, 2013 pp. 207)
Let A be the set of all Californian heads and B = {0,1,2,3,4, ..., 1000000} be the number of hairs one can have on ones' head. Let f be a function that maps A → B, for which f(x) equals the number of hairs on the head of x. Since |A|>|B|, the pigeonhole principle asserts that f is not injective. Thus there are two Californians x and y for whom f(x) = f(y), meaning they have the same number of hairs on their heads.

Example B — Subset Cardinalities

If A is any set of 10 integers between 1 and 100, then there must exist two different subsets X and Y for which the sum of elements in X equals the sum of the elements in Y.
Proof of Example A (Hammack, 2013 pp. 206)
Suppose A ⊆ {1, 2, 3, 4, ..., 99, 100} and |A| = 10. Notice that if X ⊆ A, the X has no more than 10 elements, each between 1 and 100. Therefore, the sum of all the elements of X is less than 100 × 10 = 1000. Consider the function f: 𝓟(A) → {0,1,2,3,4,...,1000} where f(X) is the sum of the elements in X.
As the cardinality of |𝓟(A)| = 2¹⁰ = 1024 > 1001 = |{0,1,2,3,...,1000}| it follows from the pigeonhole principle that f is not injective, i.e. that it is a "many-to-one" function. Therefore, there are two unequal sets X, Y ∈ 𝓟(A) for which f(X) = f(Y). Stated differently, there are subsets X ⊆ A and Y ⊆ A for which the sum of elements in X equals the sum of elements in Y.

Example C — The Chinese Remainder Theorem

Let m and n be relatively prime positive integers. Then the system x = a (mod m), x = b (mod n) has a solution.

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?
Proof of Example C
First consider the sequence
(1) b, b + m, b + 2m, ..., b + (n - 1)mThe sequence forms a complete residue class, modulo n. To see this, consider the sequence:(2) 0, m, 2m, 3m, ..., (n - 1)mSince the greatest common divisor of (m,n) = 1, we have xm ≡ ym (mod n) <=> x ≡ y (mod n). Hence, each element in the sequence (2) is unique. Adding b to the sequence (1) only cyclically permutes the residue class.By the pigeonhole principle, for any 0 ≤ a < n, we must have b + km ≡ a (mod n) for any k ∈ {0,...,n − 1}.

Constructive vs Non-Constructive Proofs

There exist irrational numbers x, y for which xʸ is rational
Non-Constructive Proof
Let x = √2^(√2) and y = √2. We know y is irrational, but we do not know whether x is rational or irrational. If x is irrational, then we have an irrational number to an irrational power that is rational:
xʸ = (√2^(√2))^(√2) = (√2)^(√2 × √2) = (√2)² = 2If x is rational, then yʸ = √2^(√2) = x is rational.Either way, we have an irrational number to an irrational power that is rational.
Constructive Proof
Let x = √2 and y = log(9). Then
xʸ = √2^(log(9)) = √2^(log(3²)) = √2^(2log(3)) = (√2^2)^(log(3))^= 2^(log3) = 3As 3 is rational, we have shown that xʸ = 3 is rational.We know that x = √2 is irrational. We do not know whether y = log(9) is irrational. Suppose log(9) is rational, so that there are two integers a, b for which a/b = log(9). Then 2^(a/b) = 9, so 2^(a/b)ᵇ = 9ᵇ, which reduces to 2ᵃ = 9ᵇ. However, we know that 2ᵃ is even and 9ᵇ must be odd, so they cannot equal one another. We have obtained a contradiction and must assume that log(9) is irrational.

Cantor’s Paradise

Medium’s #1 Math Publication!

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app