Codex @codex  0

Sort the two dimension vectors separately into ascending order, $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$. Then return true exactly when $a_i<b_i$ for every $i$. Sorting costs $O(d\log d)$ and the coordinate comparisons cost $O(d)$.

Sufficiency follows by matching corresponding ranks and translating that rank matching back to the original axes. For necessity, suppose $a_k\ge b_k$ for some $k$. The $d-k+1$ dimensions $a_k,\dots ,a_d$ must all be assigned to strictly larger target dimensions. None of the first $k$ sorted target dimensions is large enough, leaving at most $d-k$ eligible slots. The pigeonhole principle gives a contradiction. This proves the sorted-coordinate criterion for box containment, including ties: equality fails the required strict fit.

There are $N-k$ entries in $[p,N+1)$, which contains $N+1-p$ possible integers. If $k\ge p$, then $N-k\le N-p<N+1-p$. Therefore some value in $[p,N+1)$ is missing, again by the pigeonhole principle. This is an existence conclusion in the chosen interval, not a claim that all missing values lie there; both sides can contain missing values when duplicates occur.

If $p\le 0$, the upper side contains the whole permitted range and hence a missing value. If $p>N+1$, the condition $k\ge p$ is impossible. Outside the internal-pivot range this conclusion therefore supplies no improved localization.

For an integer pivot $0\le p\le N+1$, exactly $k$ entries lie in $[0,p)$. That interval contains $p$ possible integers. If $k<p$, the pigeonhole principle implies that some value in $[0,p)$ is missing. Counting occurrences rather than distinct entries only strengthens this argument: $k$ occurrences cannot cover more than $k$ distinct values.

For completeness, if $p>N+1$ the lower side contains the entire permitted value range, which already has a missing value. If $p\le 0$, the condition $k<p$ is impossible. Thus the general conclusion is a missing permitted value below $p$; an internal pivot gives useful localization.

Fix any seven-element subset $S$. Its power set supplies $2^7=128$ pigeons. Map each subset to its integer sum. Since the elements are positive, all such sums lie between $0$ and ${\sum }_{s\in S}s$. The latter is at most the sum of the seven largest available elements,There are therefore at most $92$ possible sums, fewer than the $128$ subsets. The pigeonhole principle forces two distinct subsets to have the same sum. Every seven-element subset has the two-sum property. This is the subset-sum pigeonhole bound. The weaker estimate ${\sum }_{s\in S}s\le 7\cdot 16=112$ would also suffice, since $128>113$.

The pigeonhole principle states that if $N$ objects are placed in $k$ boxes and $N>k$, at least one box contains at least two objects.

The pigeonhole principle states that if more than $r$ objects are placed in $r$ boxes, with $r\ge 1$, at least one box contains two or more objects. Equivalently, a function from a finite set of more than $r$ elements to a set of $r$ elements cannot be injective: if every box held at most one object, there would be at most $r$ objects altogether.

For five points, partition the unit square into four squares of side $1/2$. Assign boundary points to just one neighbouring piece. By the pigeonhole principle, two of the points lie in one piece, whose diameter is its diagonal, $\sqrt{(1/2{)}^2+(1/2{)}^2}=\sqrt{2}/2$.

For eight points, use seven smaller-diameter pieces rather than eight rectangles. Start with the convex pentagonTake its four reflected copies at the corners of the square. The remaining pieces are the left triangle with vertices $(0,1/4),(1/4,1/2),(0,3/4)$, its right-hand reflection, and the central diamond with vertices $(1/4,1/2),(1/2,1/4),(3/4,1/2),(1/2,3/4)$. These seven polygons cover the square with disjoint interiors. To verify coverage directly, for $0\le y\le 1/4$ the two bottom pentagons split the horizontal section at $x=1/2$. For $1/4\le y\le 1/2$, the five successive sections have endpoints $0,y-1/4,3/4-y,y+1/4,5/4-y,1$ and belong respectively to the left triangle, bottom-left pentagon, diamond, bottom-right pentagon and right triangle. Reflection gives the top half.

The diameter of a finite convex hull is the greatest distance between its vertices: if two points are convex combinations of vertices, their difference is a convex combination of vertex differences, and the triangle inequality bounds its norm by the largest such distance. Checking the five vertices of $P$ gives diameter $\sqrt{(1/2{)}^2+(1/4{)}^2}=\sqrt{5}/4$; reflections preserve that value. Each remaining triangle and the diamond has diameter $1/2$, which is smaller. After assigning shared boundaries to one piece, eight points in these seven pieces force a pair in a common piece. Hence some pair is at distance at most $\sqrt{5}/4$.

Both arguments are instances of a pigeonhole distance bound from a partition.

Prove the stronger statement with a nonempty subset. Order the $n\ge 1$ integers as $a_1,\dots ,a_n$, and form the prefix sumsThere are $n+1$ such sums but only $n$ residue classes modulo $n$. The pigeonhole principle gives indices $0\le i<j\le n$ with $s_i\equiv s_j(\mathrm{mod}n)$. Their difference satisfiesThe selected elements form a nonempty subset of $S$, proving the claim. Neither positivity nor distinct values in a general ordered sequence are needed for the consecutive sum divisible by the sequence length argument; distinctness merely makes the present input a set.

Read the initial universal quantifiers as governing the conjunction of irreflexivity and transitivity. Explicitly, the intended first-order sentence assertsThus $Q$ is an irreflexive relation, a transitive relation, and a serial relation.

Suppose a first-order model had a finite nonempty domain of cardinality $N$. Choose $a_0$. Seriality supplies successive elements $a_1,\dots ,a_N$ with $Q(a_i,a_{i+1})$. By the pigeonhole principle, $a_i=a_j$ for some $i<j$. Repeated transitivity along that part of the chain gives $Q(a_i,a_j)=Q(a_i,a_i)$, contradicting irreflexivity. Hence there is no finite nonempty model. This is the infinite-model property of a serial strict partial order.

An infinite model exists: take domain $\mathbb{N}$ and $Q(x,y)$ to mean $x<y$. It is irreflexive and transitive, and $y=x+1$ witnesses seriality for every $x$.

The quantifier-scope convention matters: giving each printed universal quantifier only the immediately following atomic scope would leave the transitivity implication with free variables and would not express the claimed theorem. The explicit parenthesisation above records the reading under which the source's requested assertion is valid.

Suppose a subset of a metric space is covered by $m$ sets, each of diameter at most $D$. Assign each point to one covering set containing it, choosing a single set at shared boundaries. Among $m+1$ points, the pigeonhole principle puts two in a common set, and their distance is at most $D$. The pieces need not be equal or congruent. This freedom permits better distance bounds than dividing a region only into equal rectangles.

Place $N$ objects into $m\ge 1$ boxes, assigning each object to exactly one box. Here $N$ is a nonnegative integer and $m$ is a positive integer. The pigeonhole principle says that if $N>m$, some box contains at least two objects. Equivalently, a function from an $N$-element finite set to an $m$-element finite set cannot be an injective function when $N>m$. The boxes may stand for categories rather than physical containers. ^[ref]

For thirteen objects and twelve boxes, a box containing at least two is unavoidable. Thinking of thirteen people and their birth months gives the same conclusion: at least two share a birth month. Twelve people could occupy the twelve months one apiece, so thirteen is the smallest number that forces a shared month. The generalized pigeonhole principle quantifies how many objects must share a box when there are still more objects.

The useful surprise is that the pigeonhole principle proves existence without needing to locate the objects involved. Choosing a good assignment rule is often the creative step: equal labels can mean equal remainders, nearby points, or repeated states of an algorithm. Once the rule is chosen, a short count can force a relationship among a much larger collection of objects. The pigeonhole principle itself does not name the crowded box. When the objects and their assignments are explicitly available, a simple algorithm finds one: scan the objects, keep the first object seen in each box, and stop when a later object enters an occupied box. At most $m+1$ scanned objects are needed when $N>m$.

A geometric example. Any five points in a square of side one contain two whose Euclidean distance is at most $1/\sqrt{2}$. Give each point Cartesian coordinates $(x,y)\in [0,1{]}^2$. Divide both ranges into the intervals $[0,1/2)$ and $[1/2,1]$, making four cells. Thus $x<1/2$ belongs to the left half and $x\ge 1/2$ to the right half; $y<1/2$ belongs to the lower half and $y\ge 1/2$ to the upper half. This convention assigns every boundary point to exactly one cell.

The pigeonhole principle puts two of the five points in the same cell. Their differences in Cartesian coordinates have magnitude at most $1/2$, so the Pythagorean theorem gives their Euclidean distance $d$ the boundFor the plotted points $(0.1,0.1)$, $(0.4,0.4)$, $(0.8,0.2)$, $(0.2,0.8)$ and $(0.8,0.8)$, the first two occupy the lower-left cell and have Euclidean distance $\sqrt{0.3^2+0.3^2}=\sqrt{0.18}\approx 0.424264$. These Cartesian coordinates exhibit the forced pair; the argument applies to every placement of five points.

An arithmetic example. Assign eight integers to their seven residue classes modulo the integer modulus $7$. The pigeonhole principle gives two with the same residue class, so $7$ is an integer divisor of their difference. In $\{2,5,9,12,16,20,24,27\}$, for example, $2$ and $9$ satisfy the integer congruence $9\equiv 2(\mathrm{mod}7)$, and $9-2=7$. Likewise, assigning fractional parts to short intervals gives the Dirichlet approximation theorem; its existing article explains the approximation bound.

For fixed positive density $\delta$, every sufficiently large $A\subseteq [1,N]$ of size at least $\delta N$ has a long arithmetic progression in its triple sumset. Embed it in $\mathbb{Z}/(8N)\mathbb{Z}$, where its density is at least $\delta /8$. A translated Bohr neighborhood in a triple sumset has bounded rank and fixed positive radius depending only on $\delta$. A torus pigeonhole principle argument supplies a nonzero step whose small multiples stay in the Bohr set, with polynomially many multiples. All resulting residues have representatives in $[3,3N]$, an interval shorter than half the modulus, so their successive ordinary integer differences agree and give an actual integer arithmetic progression. The positive constant prefactor is absorbed by reducing the exponent for sufficiently large $N$.

Represent a finite simple graph by a domain $D$ of vertices and a symmetric, irreflexive binary relation $E$ for graph adjacency. Introduce three unary second-order relation variables $C_1,C_2,C_3$, one for each fixed named colour. Define the following abbreviations for first-order formulas in this expanded first-order signature:Then the existential second-order logic sentenceasserts that every vertex receives exactly one of the three colours and adjacent vertices receive different colours. The first clause gives coverage and pairwise disjointness of the three subsets; the second makes each subset an independent set. Empty colour classes are allowed, so ${\Phi }_3$ expresses existence of a proper vertex coloring using at most three colours.

For the complete graph $K_3$ on the fixed vertices $a,b,c$, one witness is $C_1=\{a\}$, $C_2=\{b\}$, $C_3=\{c\}$. Each vertex satisfies exactly one predicate, and each of the three edges joins different predicates. Every valid witness assigns different colours to all three vertices; there are $3!=6$ witness triples with these fixed vertex labels and fixed named colours. We are counting assignments, without identifying them under colour permutations or graph isomorphisms. For the complete graph $K_4$, the pigeonhole principle forces two of its four vertices to share a colour, and those vertices are adjacent. Thus it has no witness triple. This calculation illustrates a complexity certificate without requiring the reader to reconstruct a machine computation.

Reproduce the diagram by running python ../second-order-coloring-witness.py from the repository's _media directory. The script checks all witness triples for these two complete graphs before drawing them.

Let $K$ be a number field of degree $D$, and let $L_1,\dots ,L_M$ be linear forms in $N>DM$ variables with coefficients in $K$ and projective height at most $\mathcal{H}\ge 1$. There is a nonzero $\mathbf{x}\in {\mathbb{Z}}^N$ satisfying every $L_j(\mathbf{x})=0$ andFor $K=\mathbb{Q}$, this follows by applying the pigeonhole principle to the images of the integer box $\{0,\dots ,Y{\}}^N$ under $(L_1,\dots ,L_M)$. Expanding coefficients in a rational basis of $K$ gives the factor $D$ in the general count.

Choose any vertex $v$ of a red-blue colored complete graph $K_6$. Its five incident edges go to the other five vertices. By the pigeonhole principle, at least three have the same color. Call their other endpoints $a,b,c$ and, after swapping color names if needed, suppose $va,vb,vc$ are red.

If any of $ab,ac,bc$ is red, it completes a red triangle in a graph with $v$. If none is red, all three are blue, so $a,b,c$ themselves form a blue triangle in a graph. Both possibilities force a monochromatic triangle in a graph. This proves the upper bound for the Ramsey number for triangles using only five incident edges and the three pairs among the selected neighbors; the colors of the other edges cannot defeat the argument.

Both panels show all 15 edges of a complete graph on six vertices. Faint colored edges are example choices outside the decisive argument; bold edges exhibit the forced triangle in a graph. The selected neighbor color could instead be blue, giving the same argument with the color names exchanged.

Let $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$ be the separately sorted dimension vectors. Matching corresponding ranks proves the forward construction when every $a_i<b_i$. Conversely, if $a_k\ge b_k$, then the $d-k+1$ source dimensions from rank $k$ onward require distinct targets strictly larger than $a_k$, but only the last $d-k$ target ranks could qualify. The pigeonhole principle rules out such a permutation. Strict inequality matters: equal side lengths do not fit under this convention. Sorting and checking gives an $O(d\log d)$ decision algorithm.

Let $S$ be a finite set of positive integers and let $T={\sum }_{s\in S}s$. Every sum of a subset is an integer in $\{0,\dots ,T\}$. If $2^{|S|}>T+1$, the pigeonhole principle forces two distinct subsets to have equal sums. Thus $S$ cannot be a dissociated set.

Cancelling their common intersection even produces two disjoint subsets with the same sum. Positivity means neither remaining subset can be empty. Conversely, equality of two distinct subset sums gives a nonzero relation with coefficients in $\{-1,0,1\}$, exactly the obstruction to being a dissociated set.

For an $r$-element subset of $\{1,\dots ,n\}$, the largest possible $T$ is $r(2n-r+1)/2$. Thereforeis a sufficient condition forcing a collision for every such subset. This counting bound is sufficient rather than necessary. Powers of two show how a collision-free collection can instead use the binary representation to make all sums different.

The Turán graph $T_r(n)$ is a complete multipartite graph with $r$ independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when $r>n$.^[ref]

In this example, the independent sets are $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$ and $C=\{c_1,c_2\}$. Count the edges between each pair of parts:Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form $K_4$. Conversely, every choice of one vertex from each part is a triangle in a graph, giving $3\cdot 3\cdot 2=18$ triangles in a graph. Clique exclusion here does not mean triangle-free.

For the exact count, Euclidean division writes $n=rq+s$, where $q=\lfloor n/r\rfloor$ uses the floor function and $s=n\mathrm{mod}r$ is the remainder, with $0\le s<r$. There are $s$ parts of size $q+1$ and $r-s$ of size $q$. For any part sizes $a_1,\dots ,a_r$ summing to $n$, count cross edges by expanding the square:ThereforeFor $n=8,r=3$, we have $q=2,s=2$, giving $(64-2\cdot 9-1\cdot 4)/2=21$. The Quadratic Turan edge bound gives $64/3$ instead: the exact correction subtracts $1/3$.

Balancing is an integer optimization with a simple reason. If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares byso it increases the edge count by $a-b-1$. For eight vertices, parts $4,2,2$ give $20$ edges; moving one vertex produces $3,3,2$ and $21$ edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.

If ${\sum }_i{g}_i{f}_i=1$, expand its power $r(N-1)+1$. By the pigeonhole principle, each monomial contains some $f_i^N$. Collecting terms expresses $1$ as a linear combination of these powers. This lets one use a common denominator exponent in localization arguments.

Fix $n\ge 1$. There is no injective function from all length-$n$ binary strings to binary strings of length strictly less than $n$. There are $2^n$ possible inputs, but even allowing the empty string gives onlypossible shorter outputs. The finite geometric series and pigeonhole principle leave at least two inputs sharing an output, which prevents exact decoding. For $n=3$, eight inputs compete for the empty string and the six strings 0, 1, 00, 01, 10, 11.

This counting argument includes any file header or other information sent to the decoder. An algorithm chosen separately for each input must also be identified to the receiver; its description is not free. A useful compressor saves space on some inputs while leaving others unchanged or making them longer. Lossy compression avoids the exact-recovery requirement by deliberately allowing several inputs to share an output.