Skip to content

Pigeonhole Principle

Definition

The Pigeonhole Principle, also known as the Dirichlet drawer principle.

It is often used in existence proofs and for finding worst-case solutions.

Simple Case

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

This theorem seems rather obvious. The proof uses contradiction: assume each group contains at most \(1\) object, then the total number of objects is at most \(1 \times n\), but there are actually \(n+1\) objects, which is a contradiction.

Generalization

If \(n\) objects are divided into \(k\) groups, then there exists at least one group containing greater than or equal to \(\left \lceil \dfrac{n}{k} \right \rceil\) items.

The generalized form can also be proved by contradiction: if each group contains fewer than \(\left \lceil \dfrac{n}{k} \right \rceil\) objects, then the total sum \(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\), which is a contradiction.

Furthermore, the condition of partition can be weakened to cover, and the conclusion still holds.
Given a set \(S\) and a family of non-empty subsets \(\{A_1,A_2\ldots A_k\}\) of \(S\):

  • If \(\bigcup_{i=1}^k A_i = S\), it is called a cover of \(S\).
  • 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 \(\{A_1,A_2\ldots A_k\}\) of \(S\), there exists at least one set \(A_i\) such that \(\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil\).

References

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用