Thinking Like a Mathematician
The quintessential counting argument
The pigeonhole principle is a simple, yet beautiful and useful idea. Given a set A of pigeons and a set B of pigeonholes, if all the pigeons fly into a pigeonhole and there are more pigeons than holes, then one of the pigeonholes has to contain more than one pigeon.
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
The first formalization of the pigeonhole concept is believed to have been made by Dirichlet (1805?1859) as what he called Schubfachprinzip or the ?drawer/shelf principle?. As Dirichlet published works in both German and French, he would alternate between calling the principle Schubfach and tiroir, which both translate to drawer. However, as Dirichlet?s father was a postmaster it is believed that the type of drawer he was referring to might have best been translated to English as pigeon-hole, such as those commonly used for storing and sorting mail. The first appearance of the term ?pigeonhole principle? was used by mathematician Raphael M. Robinson in 1940.
Infinite sets
Georg Cantor (1845?1918) indirectly made use of the pigeonhole principle in his 1873?74 investigations of countability:
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)
Although a very simple and easily graspable concept, the pigeonhole principle is powerful enough to prove truths that are far from obvious. In a sense one of the quintessential counting arguments, the pigeonhole principle for instance allows us to prove statements such as:
- At any given time there live at least two people in California with the same number of hairs on their heads;
- You cannot cover a 8 x 8 square chess board with two diagonally opposite corners removed, with domino pieces of size 1 x 2;
- In a room full of 367 people there are at least two people with the same birthday;
- Any lossless compression algorithm that makes some inputs smaller will also make some outputs larger;
Definition
Formally, think of the pigeonhole principle as the statement about a function f from domain P ? PH, where pigeon n flies into pigeonhole f(n), as is shown below:
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)|
The three cases illustrate three types of functions from a domain (?pigeons?) to a codomain ?pigeonholes? which can be mapped to one another:
- Case A: If |n| > |f(n)|, then the function is a non-injective surjective function (not a bijection)
- Case B: If |n|= |f(n)|, then the function is a injective surjective function (bijection)
- Case C: If |n| < |f(n)|, then the function is an injective non-surjective function (not a bijection).
Case A is the case illustrating the essence of the pigeonhole principle, namely that if you put n items into m containers and n > m, then at least one container must contain more than one item. The function f that maps pigeons into pigeonholes is hence called a surjective function. We may prove the principle easily by contradiction:
Proof of Pigeonhole PrincipleSuppose 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/mNumber of pigeons < m n/mNumber of pigeons < nBut 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
As mentioned, although simple to grasp, the pigeonhole principle allows us to prove statements that sometimes seem unknowable. Statements such as:
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
To prove this, we need to establish two facts. First, that the population of California is larger than 20 million (actually it?s more like 40 million). Second, that it is a biological fact that every human head has fewer than one million hairs (typically, the number ranges between 90,000?150,000):
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.
Consider for instance the random set A = {6, 7, 11, 12, 17, 50, 51, 80, 90, 100} which has subsets X = {7, 12, 17, 50} and Y = {6, 80} for which the sum of the elements in X equals the sum of those in Y, namely 86. If we try to mess this up by changing a value in A (say, changing the 7 to a 5), we would instead get A? = {5, 6, 11, 12, 17, 50, 51, 80, 90, 100} and yet still find subsets W = {6, 12, 17, 50} and Z = {5, 80} whose cardinalities are both equal to 85.
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
The well-known Chinese remainder theorem gives the necessary conditions for multiple equations to have a simultaneous integer solution. It may be stated as:
Let m and n be relatively prime positive integers. Then the system x = a (mod m), x = b (mod n) has a solution.
The Chinese remainder theorem is useful because it establishes that if we know the remainders of the division of an integer n by several integers, then we can determine uniquely the remainder of the division of n by the product of these integers. The theorem was famously first stated as early as the third century by Chinese mathematician Sunzi:
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?
To illustrate this practically, think of a box of gold coins. We know that if the coins are equally divided among six friends, four coins are left over. If the coins are equally divided among five friends, three coins are left over. If the box holds the smallest number of coins that meets these conditions, how many coins are left when equally divided among seven friends? The answer is zero (Brilliant.org, 2019).
Proof of Example CFirst 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
Finally, a note about the type of proofs pigeonhole proofs belong to. Although useful, a defining characteristic of pigeonhole proofs are that they are non-constructive, i.e. that although they prove the existence of something, they fail to provide an explicit example that proves the theorem. To illustrate the difference, consider two proofs of the same statement, namely that:
There exist irrational numbers x, y for which x? is rational
Let us first consider a non-constructive proof (Hammack, 2013 pp. 128) that shows that there exist irrational numbers x and y for which x? is rational without actually producing an example:
Non-Constructive ProofLet 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.
Next consider an alternative, constructive proof:
Constructive ProofLet 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.
In the above proof of the same statement, in the process of constructing the proof we also provide an example of a case where the statement is true, namely for x = ?2 and y = log(9). This, one never obtains from pigeonhole- and other non-constructive proofs alone.
This essay is part of a series of stories on math-related topics, published in Cantor?s Paradise, a weekly Medium publication. Thank you for reading!
