Category:Dirichlet's Box Principle

This category contains pages concerning Dirichlet's Box Principle:

Let $S$ be a finite set whose cardinality is $n$.

Let $S_1, S_2, \ldots, S_k$ be a partition of $S$ into $k$ subsets.

Then:

at least one subset $S_i$ of $S$ contains at least $\ceiling {\dfrac n k}$ elements

where $\ceiling {\, \cdot \,}$ denotes the ceiling function.

Source of Name

This entry was named for Johann Peter Gustav Lejeune Dirichlet.