
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Pigeonhole Principle in Discrete Mathematics
The Pigeonhole Principle is an interesting and important concept in Combinatorics and Counting Theory of Discrete Mathematics. It is used to show that certain outcomes are inevitable while distributing objects into containers or categories. It sounds very basic at first glance, but the Pigeonhole Principle has greater applications across various fields in Discrete Mathematics and Computer Science.
Read this chapter to learn the fundamentals of the Pigeonhole Principle and understand its generalizations.
Understanding the Pigeonhole Principle
The Pigeonhole Principle states that "if we have more objects than containers ("pigeonholes"), at least one container must hold more than one object."
Imagine a situation where there are 20 pigeons trying to enter into 19 pigeonholes. Since there are more pigeons than pigeonholes, at least one of the pigeonholes must contain more than one pigeon. This straightforward idea lays the foundation for many mathematical proofs.

Here, at the last hole, there are two pigeons.
Formal Definition: Pigeonhole Principle
The formal definition of the Pigeonhole Principle can be stated as follows −
If k objects are placed into n pigeonholes, and k > n, then at least one pigeonhole must contain more than one object.
It is also termed as Dirichlet's Drawer Principle, named after the German mathematician Peter Gustav Lejeune Dirichlet.
Proof by Contradiction
The Pigeonhole Principle is typically proven using a method called Proof by Contradiction. The proof is simple. The idea is to assume that the opposite is True, then show that this assumption is quite impossible. Let us see how this proof works −
- Assume that each pigeonhole can hold only one pigeon.
- If that were True, the total number of pigeons would be limited to the number of pigeonholes.
- But if there are more pigeons than pigeonholes, this assumption is contradicted, proving the original claim.
Applications and Examples: Pigeonhole Principle
The Pigeonhole Principle has several applications in various fields. Some advanced and complex problems could also be solved with this solution in computer science and mathematics. Let us see some of the basic and more advanced examples to that can be solved with this principle.
Example of Birthdays in a Room
One of the most common examples is the "birthday problem." If there are 367 people in a room, and at least two of them must share the same birthday. Because there are only 366 possible birthdays (in a leap year). Since there are more people than available birthdays, the Pigeonhole Principle shows us that at least two people must have been born on the same day.
Example of Socks in a Drawer
Consider we have a drawer containing 10 black socks and 10 white socks. If we randomly take out 11 socks, the Pigeonhole Principle guarantees that we will have at least two socks of the same color. This is because there are only two possible "pigeonholes" (black or white), and once we take more than two socks, one of the colors must repeat.
Example of Multiple Students with the Same Score
Another interesting problem is like, consider a scenario where an exam is graded on a scale of 0 to 100. If a class has 102 students, the Pigeonhole Principle guarantees that at least two students must have received the same number. This is because there are only 101 possible scores (from 0 to 100), and 102 students, so at least two students must share the same number.
Generalized Pigeonhole Principle
The basic idea of Pigeonhole Principle can be extended to a generalized form, which allows us to handle more complex situations. The Generalized Pigeonhole Principle says −
If N objects are placed into k pigeonholes, then at least one pigeonhole contains at least $\mathrm{\left\lceil \frac{N}{k} \right\rceil}$ objects.
This definition indicates when the number of objects exceeds a multiple of the number of pigeonholes, the one pigeonhole will contain more than the expected share of objects. Let us see some examples to understand this generalized principle.
Check out the following advanced examples of using the Generalized Pigeonhole Principle.
Example of People Born in the Same Month
Let us consider a similar example as birthday in a room problem. Consider a group of 100 people. The Generalized Pigeonhole Principle shows that at least $\mathrm{\left\lceil \frac{100}{12} \right\rceil = 9}$ people were born in the same month. Because there are 12 months. Dividing 100 people among those months results in at least one month containing 9 or more people.
Example of Students Receiving the Same Grade
If students are getting grades not the numbers. Consider the students can receive one of five grades: A, B, C, D, or F. If there are 26 students in the class, the Generalized Pigeonhole Principle shows that at least 6 students will receive the same grade. This happens because if we try to evenly distribute the students among the five grades, one of the grades will end up with at least 6 students.
Applications in Computer Science and other fields
The Pigeonhole Principle is not just used in everyday examples. It also useful in computer science. In problems related to hashing, data storage, and networks we use this principle.
Example of Hash Functions in Computer Science
We know the idea of hashing. It is a technique that is used in computer science to map large amounts of data into smaller hash values. Since the number of possible data inputs often far exceeds the number of available hash values, the Pigeonhole Principle shows that collisions will happen. This insight is used in designing algorithms to handle these collisions efficiently.
Example of Network Connections
Next example could be in networking. Consider we are managing a computer network with a limited number of servers. If we have more workstations than available servers, the Pigeonhole Principle shows that some workstations will inevitably share a server. This idea helps network engineers optimize the distribution of workloads to avoid server overload.
Applications of Pigeonhole Principle
The Pigeonhole Principle also finds its way into more creative and surprising uses. For example −
During a month where a baseball team plays between 1 and 45 games, it can be shown that there must be some consecutive days during which the team played exactly 14 games. The Pigeonhole Principle, combined with careful choice of "pigeonholes," helps prove this.
Conclusion
In this chapter, we explained the basic concept of the Pigeonhole Principle. We started with its basic definition and then slowly moving on to more generalized versions, we explored several everyday examples, from shared birthdays to sock drawers, and then looked at more complex applications in Computer Science and Mathematics.
Along the way, we also discovered how this simple idea of distributing objects into containers can have powerful conclusions.