pigeonhole principle

Definition

The pigeonhole principle is also known as the pigeonhole principle (the pigeonhole principle).

It is often used to prove existence and to find solutions in the worst case.

Simple case

If $n+1$ objects are divided into $n$ groups, then at least one group contains two or more objects.

This theorem appears quite obvious. A proof by contradiction can be considered: if each group contained at most $1$ object, there would be at most $1\times n$ objects, but in fact there are $n+1$ objects, a contradiction.

Generalization

If $n$ objects are divided into $k$ groups, then at least one group contains at least $\left \lceil \dfrac{n}{k} \right \rceil$ objects.

The generalized form can also be proved by contradiction: if every group contained fewer than $\left \lceil \dfrac{n}{k} \right \rceil$ objects, then their total $S\leq (\left \lceil \dfrac{n}{k} \right \rceil -1 ) \times k=k\left\lceil \dfrac{n}{k} \right\rceil-k < k(\dfrac{n}{k}+1)-k=n$ would be a contradiction.

In addition, the partition can be weakened to a cover without changing the conclusion.
Given a set $S$, let a family of nonempty subsets of $S$ be $\{A_1,A_2\ldots A_k\}$.

• If $\bigcup_{i=1}^k A_i$ holds, it is called a cover of $S$ (cover).
• If a cover also satisfies $i\neq j\to A_i\cap A_j=\varnothing$, it is called a partition of $S$.

The pigeonhole principle can be stated as follows: for a cover $S$ of $\{A_1,A_2\ldots A_k\}$, at least one set $A_i$ satisfies $\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil$.

References

• Wikipedia: Pigeonhole principle
• Discrete Mathematics and Its Applications: Chapter 6, Section 1