Pigeonhole principle

The pigeonhole principle states that placing more objects into fewer containers forces at least one container to hold multiple objects. It proves existence without identifying which container does so.

Generalized pigeonhole principle: A counting theorem stating that placing n objects into k containers puts at least ⌈n/k⌉ objects in some container. It sharpens the basic guarantee from one repeated object to a lower bound on occupancy.
Erdős–Szekeres theorem: A theorem stating that every sufficiently long sequence contains a long increasing or decreasing subsequence. Its proof assigns pairs of subsequence lengths and uses the principle to show those pairs cannot repeat.
Finite set: A set containing a fixed, finite number of elements. The basic principle compares the sizes of finite sets of objects and containers.
Johann Peter Gustav Lejeune Dirichlet: A German mathematician whose work shaped number theory, analysis, and mathematical physics. The principle is also known as the Dirichlet principle because of its use in his mathematical work.
Dirichlet's approximation theorem: A theorem guaranteeing rational approximations to real numbers with bounded denominators and small error. Its proof partitions fractional parts into intervals and applies the principle to force two close values.
Proof by contradiction: A proof method that derives a contradiction from the assumption that a claim is false. Assuming every container stays below a proposed occupancy bound often contradicts the total count.
Function: A relation assigning exactly one output to each input in a specified domain. Placing objects into containers is represented by a function from objects to container labels.
Georg Cantor: A German mathematician who founded set theory and developed the theory of infinite cardinalities. Set-theoretic comparisons of cardinality provide a natural language for stating the principle.
Residue class: A set of integers that share the same remainder upon division by a fixed positive integer. Residue classes serve as containers when divisibility arguments count integers.
Combinatorial number theory: The study of number-theoretic problems using counting, finite structures, and combinatorial methods. Many applications use residue classes and finite counting to prove arithmetic properties.

Linked from 30 pages