The pigeonhole principle (also known as the Dirichlet box principle) is a counting principle that states that if we have n pigeons and k pigeonholes, where n > k, then at least one pigeonhole must contain more than one pigeon.
Proof:
We use proof by contradiction here. Suppose that k+1 or more boxes are placed into k boxes and no boxes contain more than one object in it. If there are k boxes then there must be k objects such that there are no two objects in a box. This contradicts our assumptions. So there is at least one box containing two or more of the objects.
→ Generalized Pigeonhole Principle:
If n pigeonholes are occupied by kn+1 or more pigeons, where k is a positive integer, then at least one pigeonhole is occupied by k+1 or more pigeons.
Example:
Q). If 9 books are to be kept in 4 shelves, there must be at least one shelf which contains at least 3 books.
solution:-
| The nine books can be thought of as pigeons and four shelves as pigeonholes. Then, n=4 (Pigeonholes) kn+1=9 (Pigeons) k*4+1=9 ∴k=2 So, at least 1 pigeonhole i.e. shelf is occupied by k+1=2+1=3 books. |
