Home » Science » Mathematics » What is the Pigeonhole Principle?

# What is the Pigeonhole Principle?

Imagine ten pigeons flying into your homemade pigeonhole, but you only made 9. Where does the last pigeon go? What is the story behind the whole Pigeonhole Principle?

Since London’s population exceeds the maximum number of hairs on a human’s head, the Pigeonhole Principle requires that at least two persons in London have the same amount of hairs on their heads. This mathematical principle has been around since 1624.

# The Pigeonhole Principle

The pigeonhole principle is one of mathematics’ most basic but valuable concepts. It has been recorded as early as 1624. It is commonly known as Dirichlet’s box principle or Dirichlet’s drawer principle. (Source: Jeff 560)

In its simplest explanation, the principle dictates that if ten pigeons flock to nine pigeonholes, at least one of the pigeonholes would have more than one pigeon.

In theorem: if X is the average number of pigeons per hole, where X is not an integer, then at least one pigeon hole contains the maximum allowable number of pigeons, and the remaining pigeon holes would most probably have the least number of pigeons. (Source: Geeks For Geeks)

To explain further, if n plus one object are put in n containers, then at least one container will contain two or more things. The Pigeonhole Principle is used to show results must be valid because they are “too big to fail.” This means at least two objects will have or share a property for any significant number of things with a bound or a specific number of properties. And the applications for this principle are interesting, surprising, and thought-provoking. (source: Stanford)

# Some Examples of the Principle

The first example, as stated above, demonstrates the Pigeonhole Principle as such: London’s population excluding bald people is at around 7.5 million. The maximum number of hair in an average person is about 150,000. The principle would dictate that about 50 people would have the same number of strands. (Source: Maths Careers)

Next, let’s say two or more people are reading this article who will have the same birthday. The principle will state that there are 366 possible birthdays in a leap year. This article has more than 367 readers. Therefore two of you readers have the same birthday.

Another example would be when a deck of regular playing cards. If a person picks five cards out of the 52 cards in a standard deck of playing cards, at least two out of that five cards will have the same suit. By explanation, there are four suits in a regular deck of playing cards – cloves, spades, hearts, and diamonds. Each of the five cards must belong to one of the four suits. It, therefore, would follow that two of those cards have the same suit. (Source: Mind Your Decisions

# Is There a Practical Application for This Principle?

The pigeonhole principle helps prove the Lossless Compression used in Data Sciences. Data Compression is the theory wherein real-world data can be compressed by simply omitting redundancies.

This is a critical theory used in today’s world in the form of data transfer, whether the information is transferred via the network, DVDs, thumb drives, or emails, to state a few.

The idea of Lossless Compression is to replace each bitstring of information with a shorter bitstring. However, once the shorter bitstring is decompressed, it will still reveal the intact information of the original bitstring. (Source: Stanford)

The pigeonhole principle proves Lossless Compression wherein it is only possible to compress highly repetitive data, wherein two “pigeons,” pieces of data, occupy one “pigeonhole” or place in the bitstring. (Source: Stanford)