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.