Pigeon Hole Principle

Image Courtesy: Pinterest

The Pigeon Hole Principle (PHP) says that if n+1 objects are put in n boxes then at least one box contains two or more objects. Suppose we have n holes and n+1 pigeons. These pigeons live in these n holes, then the PHP tells us that at least one or more holes has more than one pigeon.

When you first learn about it, the PHP will seem very trivial but after a few examples, you will understand why it helps in solving problems. So let us begin with the first problem.

A chess master has 11 weeks to prepare for a tournament. He decides to play at least 1 game everyday, but not to play more than 12 games a week. Can we find a succession of days during which the chess master will play exactly 21 games?

Let aᵢ be the number of games played by the chess master till the iᵗʰ day. So we have,

a₁=number of games played on 1ˢᵗ day

a₂=sum of the number of games played on 1ˢᵗ and 2ⁿᵈ day

And so on till the a₇₇.

Since we already know that this problem is an application of the PHP, we can begin by mapping the days with the holes and the games of chess with the pigeons from the previous example. Why not the other way around? (Think about it)

Now do we get anything useful by applying the PHP? No.

Now let’s make some modifications before using the PHP.

Let’s begin by observing the sequence of aᵢ’s and deduce what we can. We note that the sequence is a strictly increasing one because the player plays at least one game everyday. Also this sequence is bounded by 11 times 12, that is 132. This is because the maximum number of games played in a week is 12 and we have 11 weeks in total.

Hence, we have,

Now we add 21 to each term of inequality, we get,

a₇ denotes the number of games played till the 7th day i.e. the number of games played in a week. Since we have the number of games played in a week cannot be greater than 12, hence a₇ cannot be greater than 12.

Since, we have,

hence, numbers of the first sequence are 77 different numbers between 1 and 132.

We also have,

hence the 77 numbers of the second sequence are also different numbers from 22 to 153.

Now we define the third sequence, we get 77+77= 154 observations

Hence, the combination of the two sequences, the third sequence is 154 integers bounded by 153.

Now, we apply the Pigeon Hole Principle

Set of 154 numbers is bounded by 153 among which the first 77 observations are unequal among themselves and another 77 observations are unequal among themselves.

BY PHP, we have at least one pair of (i,j) such that aᵢ=aj+21

This means there is a succession of games that is equal to 21.

If aᵢ=aj+21, then j+1,….,i is the required succession of days.

Another application of the Pigeon Hole Principle is in the proof of the Chinese Remainder theorem (CRT):

Firstly, we will discuss a bit of the notation:

Congruency notation:

According to the Chinese Remainder Theorem, we have,

A very useful tip while solving problems in Math is to visualize the situation in which the problem has put you in. So I suggest you to keep solving problems and continue learning!

A lot of the content in this post is inspired from Uttaran Chatterjee’s class at Cheenta Academy, so feel free to check their wonderful resources.