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