Pigeonhole Principle: Statement, Examples, Generalised Version

The Pigeonhole Principle states that if n containers are occupied by more than n items, then at least one container must contain more than one item.

In this page we will study Pigeonhole Principle with its statement and examples. Also, learn about the generalised version of pigeonhole principle.

Pigeonhole Principle Statement

If n containers are occupied by more than n items, then at least one container must contain more than one item.

(OR)

If n pigeonholes are occupied by n+1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.

Example

If we have to distribute 5 chocolates among 4 children, then by the pigeonhole principle one of the children must get more than one chocolate.

Generalised Version of Pigeonhole Principle

If n pigeonholes are occupied by kn+1 or more pigeons, then at least one pigeonhole is occupied by k+1 or more pigeons.

Questions and Answers

Question 1: Find the minimum number of students in a class such that three of them are born in the same month?

Answer:

We have n=12 (number of months)

k+1=3

So k=2.

Thus, answer = kn+1 = 2×12 +1 = 24+1 = 25.

Question 2: Show that at least two people must have their birthday in the same month if 13 people are in a room.

Answer:

Here we have:

n=12 pigeonholes (number of possibilities)

pigeons = 13.

So by pigeonhole principle, we get the answer.

Question 3: Find the minimum number of students needed to guarantee that five of them belong to the same class (1st to 4th).

Answer:

Here we have:

Question 4: If 3 men and 5 women are lined up in a row, then show that at least two women will be next to each other.

Answer:

Here we have:

Question 5: Let a box contains many red, white and blue balls. Find the minimum number of balls that one needs to choose in order to get four balls are of same colour.

Answer:

Here we have:

HomePage of Discrete Mathematics

FAQs