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