---
tag: 0BY7GN3449
kind: statement
role: theorem
name: Generalized pigeonhole principle
msc: [05A05]
uses: [05099E1NMJ, 0HGVCWQGY3]
sources:
  - url: https://en.wikipedia.org/wiki/Pigeonhole_principle
    locator: Strong form
---

## Statement

Let $A$ and $B$ be finite sets, let $f : A \to B$ be a function, and let $n$ be a natural number.
Assume that $|B| \cdot n < |A|$.
Then there is an element $b \in B$ whose fibre $f^{-1}(b) = \{a \in A : f(a) = b\}$ has more than $n$ elements.

## Remarks

For $n = 1$ this is the [[pigeonhole principle|0HGVCWQGY3]].
An equivalent form: if $N$ objects go into $k$ boxes, some box has at least $\lceil N / k \rceil$ objects.
Example: among $25$ people, at least $3$ share a birth month, because $12 \cdot 2 < 25$.

## Explanations

### L1 human

If every box held at most $n$ objects, the boxes would hold at most $n$ times the number of boxes.
So if there are more objects than that, some box must hold more than $n$.