What is the pigeonhole principle: Definition, examples and proof
The pigeonhole principle is powerful enough to prove truths that are far from obvious. Although this principle may seem obvious to some, many challenging Olympiad problems can be solved by applying it.
Source: UGC
For learners to understand this concept easily, there are examples given on topics such as cards and simple sentences. Interestingly, the results come out of a basic insight from stuffing pigeons into pigeonholes in all of these examples.
What is the pigeonhole principle?
To define pigeonhole principle, it is essential to know that it is a powerful tool utilized in Combinatorial Mathematics. Understanding this concept is effectively achieved using an example or problem that requires to be solved.
If there are 51 pigeons required to fly into 50 pigeonholes, where all of the holes have to be occupied, at least one hole will have at least two pigeons.
Therefore, the pigeon hole principle states that if the number of pigeons is more than that of the pigeonholes, at least one hole will have at least two pigeons.
Generalized pigeonhole principle
To define pigeonholing in a generalized version, this concept states that the maximum value is at least the average value for any non-empty finite bag of real numbers.
When undertaking typical data analysis, the average is usually the ‘middle’ value. This means that the maximum value should be at least as big.
This generalized version may sound different, but it is mathematically the same as the one explained using pigeons and pigeonholes.
Taking into consideration the scenario stated earlier concerning pigeons required to enter pigeonholes, consider the average. If there are more than n pigeons and n holes, the average value of (pigeons/pigeonholes) is greater than one.
In simpler terms, there exists some value of more than one pigeon per hole. Therefore, the two versions explain the same concept.
Source: UGC
Pigeonhole principle proof
Pigeonhole principle: If y is a positive integer and y + 1 objects are placed into y boxes, then at least one box contains two or more objects.
Proof: We use a proof by contraposition. Suppose none of the y boxes has more than one object, then the total number of objects would be at most y. This contradicts the statement that we have y + 1 objects.
Pigeonhole principle examples
Here are some examples that will help you get a better understanding of the pigeon hole theory.
Example 1
If you are required to pick five cards from a standard deck of 52 cards, at least two will be of the same suit.
Why? This is because each of the five cards can only belong to one of the four suits. This means that two or more of the cards picked will belong to the same suit.
Example 2
For every illustration with a 27-word sequence, at least two words will start with the same letter. These sentences are a perfect example to explain this concept.
Using the example stated above, the illustration is made up of two sentences that make up a total of 27 words, excluding the number, of course. In reference to the pigeonhole principle, two of the words must start with the same letter.
Based on our example, isn’t this true? We find words such as ‘sequence, start, same, and sentences’ all start with a common letter.
Pigeon hole problems
Take a look at these problems and try to solve them before taking a look at the solution. This will help you discover if you have properly understood this concept.
Problem 1
If a man has an infinite number of four different patterns of multicolored socks in a drawer, how many socks must he pull out of the drawer to guarantee he has a pair?
Source: UGC
Solution
He must pull out five socks to ensure he has a pair. Let us assume the socks are pigeons, and the colors are holes. If he pulls out five socks, this principle states that at least two will have the same colors and pattern.
This is because it is not guaranteed that there will be a pair made if only four socks are pulled out as they could each be made up of different colors and patterns. However, the fifth one has to match one of the four.
Take a look at an advanced and complex problem:
Problem 2
Every point in a plane is either red, green, or blue. Prove that there exists a rectangle in the plane such that all of its vertices are the same color.
Solution
Consider a 4×19 grid of points in this plane. For each row of 4 points, in reference to the pigeon hole method, two must be the same color, for instance, green.
Denote such a row “green” (a row can be two colors simultaneously) and consider the colors of all 19 rows. Again, by the pigeonhole principle, seven must be the same color. Without loss of generality, assume this color is green.
Now, consider the placement of the two green points out of four in each row. There are (4/2) = six ways to place two green points in four spots, so again by the pigeonhole principle, two of the seven rows must have the same placement. By choosing the four green points in those two rows, a monochromatic rectangle is formed, as desired.
Understanding the pigeonhole principle is highly beneficial as it has facilitated solving many difficult Olympiad problems, as well as intermediate and introductory problems.
READ ALSO: What is Illusory correlation in psychology: Definition and examples
As reported by Legit.ng, illusory correlation refers to when a person perceives a relationship between two variables that are not, in fact, correlated. An example of illusory correlation is someone who visits New York and someone in the train station is rude to them. Later, they visit a restaurant to have dinner, and the waiter is rude as well. They later request an Uber to leave the restaurant and the Uber driver is unfriendly.
When this person looks back at their trip to New York, it will be easy for them to remember these unpleasant experiences and make the conclusion that people who live in that city are unfriendly and rude, overlooking the positive experiences.
Source: Legit.ng
