Assuming you have ten holes and eleven pigeons fly into these holes, then at least one hole will house more than one pigeon. This is the pigeonhole principle in Discrete Mathematics. 

What is the pigeonhole principle?

In formal definition, if there are n items, m boxes, and n > m, at least one box contains more than one item. 

Another formal definition in mathematical terms is, if there exist two sets, X and Y, with a function, f, such that f: X → (Y), and |X| > |Y|, then f is not a 1-1 function. With |X| being the size of the set, X. 

The pigeonhole principle is somewhat adjacent to the bijection rule which states that if there exist two sets, X and Y, with a function, f, such that f: X → (Y), and |X| == |Y|, then f  is a 1-1 function. 

I first heard of the pigeonhole principle earlier this year, in my Advanced Discrete Mathematics class in grad school. Not only was the name exciting, but I also found the principle and its applications very interesting and relatable. So, I decided to share it with you all based on my understanding. 

Origin of the Pigeonhole Principle

You might wonder, where did this come from?

The pigeonhole principle can be traced as far back as 1622. The first appearance of this principle was indirectly in Selectæ Propositiones, a Latin book, by Jean Leurechon, a Mathematician, French Jesuit Priest, and Astronomer, who also named the thermometer. In Selectæ Propositiones, he wrote, “It is necessary that two men have the same number of hairs, écus, or other things, as each other.” This sentence was later fleshed out properly in a book by one of his students, in 1624, in a mathematics compilation book.

However, the name was formed officially about two decades later, in 1834, when a treatment was done on the principle by Peter Gustav Lejeune Dirichlet, a German Mathematician, who made contributions to number theory and the Fourier series and was one of the first people to give a formal definition to functions. Since then, numerous generalizations and variants have been derived from this principle, which we will discuss later in this article. 

How is the pigeonhole principle applied?

The pigeonhole principle is applied in proving the correctness of a counting problem. It is useful, especially in large counting problems, where it is almost impossible or counter-intuitive to solve the problem individually and get an accurate value. One tip to determine if the pigeonhole principle is the right method to be applied is to check if the question asks you to prove the emptiness, distinctiveness, or duplicity of a grouping.

Some common examples of counting problems where the pigeonhole principle is applied are:

  1. The birthday problem: The birthday problem is an intuitive paradox that states that given 367 people in a room, at least two people share the same birthday. This can be proven using the pigeonhole principle because there are 366 days in a year (including leap years), and 367 > 366. Therefore, at least, one day in a year is the birthday of more than one person in the room. 
  2. Sock picking: Let’s assume you are given a box containing three pairs of socks, with each pair being a different color. If you are asked to blindly pick any number of socks from the box and you must guarantee that you will get a pair with matching colors from your picks, then you should pick four socks from the box. This is because there are three pairs of socks with different colors, therefore, the fourth sock picked from the box will definitely be of the same color as at least one of the socks you already picked. 
  3. Hair counting: According to Healthline, the average number of hairs on a human’s head is 100,000 and the 2020 Census Data records a 331,449,281 total population in the United States. Based on the pigeonhole principle, we can prove that at least two people in the US have exactly the same number of hairs on their heads because (331,449,281 / 100,000) > 1.

How to use the pigeonhole principle

  1. Write out your hypothesis or predicate.
  2. State that you are using the pigeonhole principle or a variant of it to prove the said hypothesis.
  3. Identify and explicitly state the pigeons.
  4. Identify and state the holes.
  5. Invoke the pigeonhole principle and use it to ascertain your claim.

Practice Exercise

Let’s go through an example where the pigeonhole principle can be applied as a proof method.

Question:
Assuming 30 students register for a class in grad school. Prove that at least two students in the class were born in the same month.

Solution:
Given that there are 30 students in the class and there are 12 months in the year. 

To prove that at least two students were born in the same month, I’ll use the pigeonhole principle.

Pigeons: 30 students

Holes: 12 months

Based on the pigeonhole principle, if m items are put into n holes and m > n, at least one hole contains more than one item. Therefore, since 30 > 12, at least one month is the birth month of more than one student in the class.

Generalizations and variants of the principle

As mentioned earlier, there have been several variants and generalizations derived from the pigeonhole principle, some of which I’ll share below.

  1. Generalized pigeonhole principle: If m is a positive integer, and there are m boxes with n items placed into these boxes, then at least one box will contain ceil(n/m) or more objects. Ceil is a function that rounds up the result from a division to the next integer.
    For example, we have 6 items placed in 4 boxes. This implies that at least one box contains 2 or more objects. 
  2. Variants and related principles:
    1. If there are n integers, k1, k2, k3, …, kn, and they have an average value > r – 1, then at least one of the integers >= r.
    2. If n objects are placed in boxes, and no box is empty, then each box has exactly one object in it.
    3. If n objects are placed in n+1 boxes, then at least one box is empty and has no object in it.

Conclusion

I hope this article was a brief introduction to the pigeonhole principle, its history, applications, generalizations, and variants, as well as, how to use it in solving discrete mathematical proofs. I have added additional links to further resources that you can check out to go through more examples and try out practice exercises.

Please feel free to drop a comment below or send an email to me: contactaniekan at gmail dot com if you have any questions, comments, feedback, or suggestions for future articles related to this. I look forward to hearing back from you. And please, share this piece with someone who needs it.

Thank you for reading.

Aniekan.

Further Readings

  1. The Pigeonhole Principle, Two Centuries Before Dirichlet
  2. http://logica.ugent.be/albrecht/thesis/Etten-intro.pdf
  3. http://pi.math.cornell.edu/~bux/teaching/Putnam/2003/w04.pdf