The pigeonhole principle

You are here: Home » education » Science and Technology » Math Initiative

E-Pao! Education - Pigeon Hole Problem

Math Initiative - I
The Pigeonhole Principle

By: Shanta Laishram *

We are starting this initiative of encouraging students who have interest in mathematics. We are trying to make them familiar with problem solving abilities which will improve their mathematical thinking and hopefully, will remove their fear of mathematical problems.

From time to time, we will pose problems which are challenging as well as exciting but do not require anything more than high school mathematics. Students who come up with solutions will be encouraged with some token appreciation either in the form of books or sponsoring them to math programs held elsewhere.

Believe us, these programs are very interesting. We will also try to interact personally with them from time to time.

In the first step towards these, we have given few problems which, we expect, all the students from Class VII onwards should be able to solve.

These problems are not difficult but they require a little bit of different thinking than those of classroom textbooks. By the ideas given in the introduction to problem and example, one should not be afraid to attempt these problems.

Please feel free to write to us about any mathematical inquiries including prospects in mathematics. You can email us at

[email protected]
or write to
Shanta Laishram
School of Mathematics,
Tata Institute of Fundamental Research,
Homi Bhabha Road, Colaba,
Mumbai-400 005, India

So, what are we waiting for, let us just begin!

The pigeonhole principle:

If m+1 or more pigeons are put into m pigeonholes, there is a hole which contains at least two pigeons!

Another way of saying is:

If n>m pigeons are put into m pigeonholes, there's a hole with more than one pigeon.

This statement, though looks simple, is very powerful and gives interesting consequences. For example, the following statement follows from the pigeonhole principle!

There are at least two people in Manipur with the same number of hairs on their heads.

One can show this as follows: A typical head of human hair has around 1,50,000 hairs. It is reasonable to assume that no one has more than 10,00,000 hairs on their head. There are more than 1,000,000 people in Manipur.

If we assign a pigeonhole for each number of hairs on a head, and assign people to the pigeonhole with their number of hairs on it, there must be at least two people with the same number of hairs on their heads.

Now can you show the following using Pigeonhole principle?

1. In a school with 500 students, there are two students who celebrate their birthdays on the same day. Show it.

2. There is a box containing many socks of black, white and yellow colors. How many socks one should pick up without looking at the colors so that one will get a matching pair in the first attempt?

3. Out of any 8 natural numbers you choose, you can get two numbers whose difference is a multiple of 7. Show it. What can you say if 8 is replaced by 10 and 7 is replaced by 9?

4. On your birthday party, you have invited 25 people. Among them, there will be 2 persons who have the same number of friends present in the party. Can you show this? (Here, A and B are friends if A is a friend of B and B is also a friend of A)!

5. The following problem is taken from Bhaskaracharya's (a Indian mathematician) 'Lilavati' (Circa 1140 A.D) and uses Pythagoras Theorem to solve it. Pigeon hole principle is not required for solving this.

"A peacock perched on the top of a nine foot high pillar sees a snake, three times as distant from the pillar as the height of the pillar, sliding towards its hole at the bottom of the pillar. The peacock immediately flies to grab the snake. If the speeds of the peacock's flight and the snake's slide are equal, at what distance from the pillar will the peacock grab the snake?"

Send in your answers to

Shanta Laishram
School of Mathematics,
Tata Institute of Fundamental Research,
Homi Bhabha Road, Colaba,
Mumbai-400 005, India

You can also send your answers by email to

[email protected]
Partial solutions are also welcome. If you can't solve all of them or solve any problem fully, you are encouraged to still submit them.

Shanta Laishram contributes regularly to e-pao.net
This Math Article was webcasted on October 15, 2006.

* Comments posted by users in this discussion thread and other parts of this site are opinions of the individuals posting them (whose user ID is displayed alongside) and not the views of e-pao.net. We strongly recommend that users exercise responsibility, sensitivity and caution over language while writing your opinions which will be seen and read by other users. Please read a complete Guideline on using comments on this website.