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).