More
CodingThe Pigeonhole Principle | Mathematics

# The Pigeonhole Principle | Mathematics

Let us suppose, we have 5 pigeons with us, and 4 pigeonholes, where pigeons can be placed. We want to place all of the 5 pigeons into the available pigeonholes.

Pigeons – P P P P P

Pigeonholes – | |    | |    | |    | |

The arrangement of the pigeons would look something like this,

|PP| |P| |P| |P|

As we can observe, there is a pigeonhole with 2 pigeons in it.

Thus, pigeonhole principle states that, if we have ‘n’ number of objects and ‘n-1’ number of buckets to place those objects, then, there would be at least 1 bucket with 2 or more objects in it.

Theorem –

I) If “A” is the average number of pigeons per hole, where A is not an integer then

• At least one pigeon hole contains ceil[A] (smallest integer greater than or equal to A) pigeons
• Remaining pigeon holes contains at most floor[A] (largest integer less than or equal to A) pigeons

Or

II) We can say as, if n + 1 objects are put into n boxes, then at least one box contains two or more objects.
The abstract formulation of the principle: Let X and Y be finite sets and let [f: A->B] be a function.

• If X has more elements than Y, then f is not one-to-one.
• If X and Y have the same number of elements and f is onto, then f is one-to-one.
• If X and Y have the same number of elements and f is one-to-one, then f is onto.

Pigeonhole principle is one of the simplest but most useful ideas in mathematics.

• Example: If (Kn+1) pigeons are kept in n pigeon holes where K is a positive integer, what is the average no. of pigeons per pigeon hole?
• Solution: average number of pigeons per hole = (Kn+1)/n
= K + 1/n
Therefore there will be at least one pigeonhole which will contain at least (K+1) pigeons i.e., ceil[K +1/n] and remaining will contain at most K i.e., floor[k+1/n] pigeons.
i.e., the minimum number of pigeons required to ensure that at least one pigeon hole contains (K+1) pigeons is (Kn+1).

Subscribe Today

Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.