In this blog post, we’ll explore what the Pigeonhole Principle is and how we can use it to logically prove the proposition that “there are at least two people in Seoul with the same number of hairs.”
What is the Pigeonhole Principle?
Let’s assume you’re currently taking an important interview—whether for a job or for graduate school. There is a piece of paper in front of you. It reads: “There are at least two people in Seoul who have the same number of hairs. Is this statement true or false?” Coming up with the answer to this question isn’t that difficult. The correct answer, as most people would guess, is “true.” However, explaining that answer logically isn’t easy. So, how should you explain it to successfully pass the interview? The way to logically solve this problem is by using the “Pigeonhole Principle.” So, what exactly is the Pigeonhole Principle, and how can it be proven?
The Meaning and Proof of the Pigeonhole Principle
Mathematically speaking, the Pigeonhole Principle states that if n+1 pigeons are placed in n pigeonholes, at least one pigeonhole must contain two or more pigeons. This Pigeonhole Principle can be adapted to various mathematical contexts depending on the situation. In some cases, it is explained by comparing pigeons and pigeonholes to “drawers and socks,” so it is also called the “Drawer Principle.” It is also known as “Dirichlet’s Box Principle,” named after the mathematician who first systematically formulated it. Let’s look at a concrete example to understand it more easily.
Suppose there are 10 pigeons and 9 pigeonholes. Our goal is to show that, given 9 pigeonholes and 10 pigeons, at least one pigeonhole must contain two or more pigeons. To prove this, let’s reverse the conclusion and assume that no pigeonhole contains two or more pigeons. For this to hold, each pigeonhole must contain at most one pigeon. Since there are 9 pigeonholes, up to 9 pigeons can be placed—one in each—but the remaining pigeon will have no pigeonhole to occupy. Ultimately, no matter which box the last pigeon enters, that box will contain two pigeons, which contradicts the initial assumption. Therefore, the initial assumption is false, and we can prove that there is at least one pigeon box containing two or more pigeons.
Why must there necessarily be people in Seoul with the same number of hairs?
Now, using the Pigeonhole Principle, we can answer the original proposition: “There are at least two people in Seoul with the same number of hairs. Is this statement true or false?” Generally, the number of hairs on a person’s head ranges from tens of thousands to, at most, about 150,000, and it is safe to say that virtually no one has significantly more than this. Furthermore, Seoul’s current population is approximately 9.3 million. If we consider each strand of hair as a separate pigeonhole and assign every person living in Seoul to a pigeonhole based on their number of hairs, the number of people far exceeds the possible number of hair strands. Therefore, there must be at least two people with the same number of hairs. This is a classic example of the pigeonhole principle in action.
In this way, the Pigeonhole Principle can be used to logically solve and prove various problems that arise in everyday life. Furthermore, the Pigeonhole Principle is widely applied not only in daily life but also in the fields of science and computer science. For example, a hash table is a data structure that stores large amounts of data in a limited amount of storage space; if there are more types of input data than there are storage locations, collisions—where different data are stored in the same location—will inevitably occur. This is an unavoidable phenomenon due to the Pigeonhole Principle. Furthermore, there can be no lossless compression algorithm that consistently compresses all files to a size below a certain threshold while still allowing for the perfect restoration of the original files. Since the number of possible original files exceeds the number of possible compressed results within a given size limit, it is inevitable that two different files will be compressed into the same result; when this happens, the original files cannot be accurately restored. Understanding the Pigeonhole Principle in this way is extremely helpful not only in daily life but also in logically understanding and solving problems in various scientific and computer science fields.
