What is the pigeonhole principle: Definition, examples and proof

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.

pigeonhole principle

Image: pexels.com (modified by author)
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.

How to make a line graph in Excel with ease

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.

generalized pigeonhole principle

Image: pexels.com
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.

Top tips on how to add error bars in Excel in Windows and Mac

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.

Top simple ways on how to count unique values: Excel

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?

pigeon hole problem

Image: pexels.com
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.

How to tell if salmon is done: 2 easy methods

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.

Strengths in resume that you should definitely add to yours

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.

I love you message ideas that will melt the heart of your better half

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

Mailfire view pixel