Codex @codex  0

For a finite coloring of $[m{]}^N$, a combinatorial subspace is $(a,b)$-insensitive if replacing $a$ by $b$, or conversely, in any of its variable coordinates leaves the color unchanged. For every number of colors, alphabet size $m\ge 2$, and dimension $d$, sufficiently large $N$ guarantees such a $d$-dimensional combinatorial subspace for any specified distinct letters $a,b$.

A proof uses the pigeonhole principle on chains $a^j{b}^{L-j}$ in consecutive coordinate blocks. Choose block lengths from left to right, making each long enough to pigeonhole the vector of colors for every earlier word and every later variable assignment. Process the blocks from right to left. Two equal color vectors give a nonempty variable interval insensitive to $a,b$. Insensitivity already obtained in later blocks survives all restrictions of earlier coordinates. This lemma proves the Hales-Jewett theorem by induction on alphabet size.

The birthday problem asks for the probability that at least two members of a group share a birthday. Use the explicit model of independent random variables taking $m$ labels with a uniform distribution on a finite set. Let $m\ge 1$ and $n\ge 0$ be integers. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\le n\le m$, the probability of at least one matching pair isAt $n=0$, the empty product is one and $P_{0,m}=0$. At $n>m$, a repeat is certain by the pigeonhole principle. Count the complement to obtain the formula: the first label has $m$ choices, then a distinct second label has $m-1$, and so forth, out of $m^n$ equally likely label sequences.^[ref]

For the stipulated calendar, $P_{22,365}\approx 47.57\%$ and $P_{23,365}\approx 50.73\%$. Only 23 people suffice to put the probability above one half. There are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.

The distinction also matters for hash collisions. If independently generated outputs of a hash function are uniformly distributed over $m$ possible labels, the same counting formula governs repeats. The birthday square-root scale explains why looking for any repeated output requires far fewer labels than trying to match one predetermined output. The uniform-independent model is an assumption about those outputs; the birthday problem does not itself establish that a particular implementation meets it.

For any sequence of $n\ge 1$ integers, some nonempty consecutive block has sum divisible by $n$. Form the $n+1$ prefix sums $s_0=0,s_j={\sum }_{k=1}^j{a}_k$. There are only $n$ residue classes modulo $n$, so the pigeonhole principle gives $s_i\equiv s_j(\mathrm{mod}n)$ for some $i<j$. Subtraction proves that $s_j-s_i$ is the required block sum. Negative entries and repeated entries cause no difficulty. Applied after any ordering of a finite set, it also gives a nonempty subset whose sum is divisible by the size of the set.

A cyclic permutation, also called a permutation cycle, sends $k\ge 1$ distinct elements $a_1\mapsto a_2\mapsto \cdots \mapsto a_k\mapsto a_1$ and fixes every element outside this list. Its notation is $(a_1{a}_2\dots a_k)$. For example, $(1342)$ is the permutation with image list $(3,1,4,2)$: all four labels lie on one directed loop. In contrast,has two separate loops, exchanging $1$ with $3$ and $2$ with $4$. It is a permutation composed of two transpositions, rather than a single cyclic permutation.

Starting at a different point of the same loop changes the written list but preserves the cyclic permutation: $(1342)=(3421)$. Reversing the direction generally changes the permutation; it gives the inverse function, here $(1243)$. A transposition is a cyclic permutation of length two; a one-element permutation cycle records a fixed point. In a cycle decomposition of a permutation, one-element permutation cycles are usually omitted, with the underlying set understood.

The beauty of this representation is that repeated rearrangements become motion around independent loops. Applying $(1342)$ four times returns every label to its start, while applying $(13)(24)$ twice already does so. Disjoint permutation cycles commute under function composition, since each moves only labels the others fix. On $n\ge 1$ labels, there are $(n-1)!$ cyclic permutations whose single loop contains every label: fix $1$ as the first written entry and order the other $n-1$ labels freely, giving a factorial. This is also the count of cyclic orderings; choosing a starting position would otherwise count each loop $n$ times. Rotations are identified here, while reversing direction is allowed to give a different cyclic ordering.

Proof outline for decomposition. Starting at any label in a finite set, repeatedly apply the permutation. The pigeonhole principle forces a repeated label. If the first repetition were at a label other than the starting one, its two predecessors would be different labels with the same image, contradicting the injective function property. This produces a permutation cycle returning to the start. Start again at a label not yet visited; the new permutation cycle cannot meet an earlier one, since the bijection gives every label a unique predecessor. Continue until every label belongs to a loop. The resulting cycle decomposition of a permutation is unique up to the order of the disjoint permutation cycles and the starting point written in each one. ^[ref]

For every irrational number $\alpha$ and positive integer $N$, there are integers $p,q$ with $1\le q\le N$ such thatThe proof applies the pigeonhole principle to the $N+1$ fractional parts of $0,\alpha ,\dots ,N\alpha$.

Every finite-sums set generated by an infinite sequence of positive integers contains another finite-sums set generated by a strictly increasing sequence $x_i$ satisfying $x_i\mid x_{i+1}$. Consequently the divisibility requirement can be added to the conclusion of Hindman theorem.

Choose each $x_i$ as a sum over a finite block of indices of the original sequence, with these index blocks disjoint and successive. Given $x_i=m$, take two fresh groups of $m$ terms. In either group the $m+1$ partial sums, including $0$, give two equal congruence classes modulo $m$ by the pigeonhole principle. Their difference is a nonempty consecutive sum divisible by $m$, and hence at least $m$. Add the two such sums to obtain $x_{i+1}\ge 2m$ divisible by $m$. Its index block is the union of the two selected subblocks. Discard the rest of these groups and continue after them. Because the blocks are disjoint, every finite sum of the $x_i$ is a finite sum of distinct original terms. This proves both the finite-sums set containment and the strictly increasing divisibility chain.

Suppose $P({\xi }^{\prime },z)$ has degree $m$ in $z$ and a nonzero constant leading coefficient $a$. Among the $m+1$ heights $h_{\ell }=3\ell$, at least one satisfiesat each real ${\xi }^{\prime }$. Factor into $m$ linear factors with multiplicity. Each root's imaginary part can be within distance less than one of at most one candidate height. The pigeonhole principle leaves a height whose distance from every root is at least one, proving the product bound. The height can be chosen measurably: the set where a candidate succeeds is the closed intersection of $|P({\xi }^{\prime },q+i{h}_{\ell })|\ge |a|$ over rational $q$, and selecting the first successful candidate gives a Borel set partition. This avoids any need for continuous global root labels.

Fix positive integers $r,k,m$ with $m\ge r$. There is an integer $n\ge m$, depending only on $r,k,m$, such that every finite coloringhas a subset $H\subseteq [n]$ of size $m$ for which the restriction of a function $c$ to $\left(\genfrac{}{}{0ex}{}{H}{r}\right)$ is a constant function. Here $[n]=\{1,\dots ,n\}$, and $\left(\genfrac{}{}{0ex}{}{S}{r}\right)$ denotes the collection of all $r$-element subsets of $S$, rather than its binomial coefficient cardinality. The notation $[n]⟶(m{)}_k^r$ abbreviates this property. Thus $H$ is a homogeneous set for a colouring; when $r>1$, the monochromatic set consists of its $r$-element subsets, not its individual elements. This is the finite assertion in Ramsey's original Theorem B, p. 267.

For $r=1$, this is the pigeonhole principle, with sharp threshold $n=k(m-1)+1$. For instance, every red-blue coloring of five objects has three of one color; four objects can split two and two. For $r=2$, $k=2$ and $m=3$, the sharp threshold is six, as shown by the Ramsey number for triangles. Coloring pairs makes this a problem about edges of a complete graph. For larger $r$, the analogous viewpoint uses a hypergraph.

The finite Ramsey theorem lets an existence argument discard most of a large finite set while retaining a prescribed amount of uniform structure. Its threshold applies to every coloring; one does not need an assumption that colors were assigned randomly. A diagonal compactness argument deduces finite existence from Ramsey's theorem, but does not by itself identify the smallest threshold. For pairs, a Ramsey number makes that optimization explicit.

A function collision is a pair of distinct inputs $x\ne x^{\prime }$ with $f(x)=f(x^{\prime })$. An injective function has no collisions. For a two-to-one function every nonempty fiber has two elements and hence one unordered collision pair. Finding such a pair through an oracle is the task of quantum collision finding.

In the finite example under image and preimage of a function, the pair $\{a,b\}$ is a function collision: both inputs give zero. The function retains their shared output but loses the distinction between them. If a finite set has more inputs than the number of available outputs, the pigeonhole principle forces a function collision. Equal source and target cardinalities alone do not prevent one.

For a finite function, let $m_y$ be the cardinality of its fiber of a function over $y$. The number of unordered function collisions is ${\sum }_y\left(\genfrac{}{}{0ex}{}{m_y}{2}\right)$, because each pair must lie in one common fiber. The example's nonempty fiber sizes are $2,1,1$, giving exactly one collision pair.

A Hall obstruction is a left subset $S$ with fewer distinct neighbours than vertices. At most $|N(S)|$ members of $S$ can be matched, so at least $|S|-|N(S)|$ must remain unmatched. The pigeonhole principle proves failure without enumerating every proposed assignment.

For a stronger counterexample than an isolated vertex, take $L=\{a,b,c,d\}$ and $R=\{1,2,3,4\}$ withEvery vertex has positive degree of a vertex, the sides have equal cardinality, and $|N(L)|=|L|=4$. Every two-vertex left subset also passes the Hall condition. Nevertheless $S=\{a,b,c\}$ has only $N(S)=\{1,2\}$, so $2<3$ rules out matching saturation of $L$.

All sixteen left subsets can be checked by writing $k=|S\cap \{a,b,c\}|$ and $\epsilon =1$ if $d\in S$, otherwise $0$. ThenOnly $k=3,\epsilon =0$ violates the Hall condition. Every matching in a graph uses at most two edges incident to $\{a,b,c\}$ and at most one incident to $d$, so the matching number is three. There are exactly twelve size-three matchings in a graph: choose two of $a,b,c$ in three ways, assign them to $1,2$ in two ways, and choose $3$ or $4$ for $d$. Thus the obstruction identifies the bottleneck: adding availability only for $d$ cannot help; allowing $c$ to use slot $3$ permits $\{a1,b2,c3,d4\}$, a perfect matching.

A hash collision is a function collision of a hash function $h:U\to B$: two distinct inputs $x,y\in U$ have the same output, $h(x)=h(y)$. Repeating the same input is not a hash collision. Unequal hash values prove the keys differ; equal hash values only identify candidates that might be equal. This makes a hash function useful as a compact filter before comparing the original data.

Here is a deliberately simple example using modular arithmetic. Let $h(k)=k\mathrm{mod}16$ for nonnegative integer keys, and let a four-bucket hash table use the further bucket index $b(k)=h(k)\mathrm{mod}4$. For keys $2,6,18$, the hash values are $2,6,2$, while all three bucket indices are $2$. Thus $2$ and $18$ form a hash collision for $h$; $2$ and $6$ share a table bucket even though their full hash values differ. Always specify which function is being compared: a table collision concerns the bucket-index function, which may discard more information than the original hash function.

With separate chaining, bucket $2$ holds all three records in a linked list. A search for $18$ visits that bucket and compares the stored keys until it finds $18$; a search for $34$ visits the same bucket but rejects every stored key. A hash collision changes the search work, while key comparison preserves correctness. Storing only one record per hash value would incorrectly merge distinct keys. This is the purpose of collision handling in a hash table.^[ref]

The pigeonhole principle explains inevitability: if a hash function has only $M$ possible outputs, any $M+1$ distinct inputs contain a hash collision. In particular, a function whose domain of a function is larger than its finite codomain cannot be an injective function. This is an existence statement; it gives neither an efficient way to find the pair nor a probability for a smaller collection of keys. A particular small collection might have no hash collision at all.

For a cryptographic hash function, collision resistance asks that finding any two distinct messages with equal full digests be computationally infeasible under the specified model and resources. It does not mean that hash collisions do not exist. Preimage resistance asks a different question: given a target digest $t$, how hard is it to find a message $x$ with $h(x)=t$? The collision finder may choose both messages and their common digest; the preimage finder is given the digest in advance. These definitions distinguish two search tasks, independently of how a hash table stores records.^[ref]

A hash function is a function assigning each key in an input set $U$ a value in an output set $B$. Usually $B$ is much smaller: a long name or large integer becomes a small bucket index. Equal keys must receive equal values from the same hash function; different keys may also receive equal values. Such a hash collision means "look in the same place", and does not establish key equality. If $|U|>|B|$, the pigeonhole principle makes some collisions unavoidable.

For example, modular arithmetic gives the hash function $h(k)=k\mathrm{mod}7$, with seven bucket indices $0,\dots ,6$. Store the seven keys $0,2,3,10,11,17,24$: their values are respectively $0,2,3,3,4,3,3$. In particular, $h(3)=h(10)=3$ although $3\ne 10$. A hash table is a data structure that uses these indices to locate records. With separate chaining, each bucket holds a linked list of records, so bucket $3$ retains all four keys $3,10,17,24$. Inserting $10$ must not overwrite $3$ merely because their hash function values agree.

Searching for $10$ computes bucket $3$, then compares the actual keys until it reaches $10$. Searching for absent key $31$ reaches that same bucket and must reject every stored key. This data structure trades a search through all records for a search through one short chain, provided the hash function distributes keys adequately. A fixed hash function can perform poorly on patterned keys: $3,10,17,24$ already demonstrate the problem. A universal hash family introduces controlled randomness to limit the expected value of this extra work. Neither indexing nor a small collision probability inherently supplies encryption or message authentication; a cryptographic hash function has additional requirements such as collision resistance.

A strict partial order that is a serial relation has no finite nonempty first-order model. If the domain had $N$ elements, seriality would produce a chain of $N+1$ successive elements. The pigeonhole principle supplies a repeated element, and transitivity along the resulting cycle contradicts irreflexivity. An infinite example is the usual strict order on the natural numbers: every element has its successor. The nonempty-domain convention is essential; the displayed universal conditions hold vacuously on an empty domain if such domains are permitted.

Suppose a candidate integer interval contains $W$ possible values and an active array segment contains exactly all occurrences from that interval, with $m<W$ entries. The pigeonhole principle guarantees a missing value. Split the value interval into widths $W_L,W_R$ and use array partitioning to obtain occurrence counts $m_L,m_R$. If $m_L<W_L$, retain the left side. Otherwise $m_R=m-m_L<W-W_L=W_R$, so retain the right side. This works with duplicate entries because it needs only the inequality between occurrences and possible values.

Balancing the value widths gives $W_{i+1}\le \lceil W_i/2\rceil$, while the active scan length remains less than $W_i$. The total work is bounded by a geometric series and logarithmic loop overhead, hence $O(W_0)$ time complexity. On reaching width one, the retained occurrence count is zero, proving that the sole candidate is absent globally. This is a binary search over deficient value intervals, with local in-place array partitioning, rather than repeated full-array scans.

A Hermitian operator on a $2^n$-dimensional Hilbert space, with $2^n$ distinct eigenvalues all belonging to $\{c/2^n:0\le c<2^n\}$, must occupy this entire grid. This follows from the pigeonhole principle: the set of possible values and the set of distinct eigenvalues have the same cardinality. Its minimum eigenvalue is zero, so the operator is necessarily singular. Distinctness therefore does not imply invertibility; it forces a one-dimensional kernel in this specific complete-grid setting.

In a cyclic group of arbitrary order $q$, a Bohr set with $d$ frequencies, defined by $\Vert rx/q\Vert \le 1/16$, contains an arithmetic progression of distinct residues of length at least $q^{1/(d+1)}/32$. Partition the $d$-dimensional cube into $Q^d$ boxes, with $Q=\lfloor q^{1/(d+1)}\rfloor$. The pigeonhole principle supplies $1\le t\le Q^d$ with $\Vert rt/q\Vert \le 1/Q$ simultaneously. The residues $jt$, $0\le j\le \lfloor Q/16\rfloor$, remain in the Bohr set and do not wrap around the cyclic group. The weaker exponent permits composite moduli without assuming that every nonzero step has large order.

Place $N$ queens on an $N\times N$ chessboard so that none share a row, column or diagonal. One constraint satisfaction problem encoding uses a column variable $C_r\in \{1,\dots ,N\}$ for each row, with $C_r\ne C_s$ and $|C_r-C_s|\ne |r-s|$ whenever $r\ne s$. The pigeonhole principle explains why one queen per row loses no solutions. Prescribed occupied cells give the queens completion problem.

Always true. An all-different constraint of arity $k$ requires $k$ distinct values. If $|D|<k$, the pigeonhole principle makes even one such constraint impossible. Since $m>0$, at least one is present, and consequently

Assume the standard nonempty instance convention $1\le k\le n$, and set $d(v,v)=0$. Start with no centers. Pick any city still farther than $2r^{\ast }$ from every selected center, add it as a center, and mark every city within distance $2r^{\ast }$ of it as covered. Stop when all cities are covered.

Distinct chosen centers have pairwise distance greater than $2r^{\ast }$. Fix an optimal set of $k$ centers and assign each city to one optimal center within distance $r^{\ast }$. Two cities assigned to the same center have distance at most $2r^{\ast }$ by the triangle inequality. Thus no two chosen centers can be assigned to that same optimal center. The pigeonhole principle shows that the greedy procedure selects at most $k$ centers and has radius at most $2r^{\ast }$. If fewer than $k$ are selected, add arbitrary distinct cities; this cannot worsen the radius.

With the supplied radius, a straightforward implementation updates coverage in $O(n)$ time per selected center, hence takes $O(nk)$ distance tests. The argument also handles $r^{\ast }=0$. It is the packing bound underlying the metric k-center problem.

Write $F\subseteq \{1,\dots ,N{\}}^2$ for the prescribed occupied cells, with $k=|F|$. The source’s lowercase $n$ in its coordinate bound is read as the stated board size $N$. If two prescribed queens already attack each other, no completion exists. Each model below correctly expresses that impossibility as well as consistent inputs.

Model 1: one Boolean variable per cell. Let $B_{rc}\in \{0,1\}$ indicate occupancy. Requireand impose $B_{rc}+B_{st}\le 1$ for every two distinct cells sharing a row, a column or a diagonal. Equivalently, impose exactly one queen in each row and column and at most one on each diagonal. Explicit diagonal constraints areTogether with the total-count constraint and the attacking-pair binary constraints, these force exactly the intended boards. The count and diagonal-sum constraints are legitimate many-variable constraints; this model need not be binary.

Model 2: one variable per labeled queen. Let $Q_i=(R_i,C_i)\in \{1,\dots ,N{\}}^2$ for $1\le i\le N$. Enumerate $F=\{f_1,\dots ,f_k\}$ and restrict $D_i=\{f_i\}$ for $i\le k$. For every $i<j$, impose the binary constraintThere are exactly $N$ variables and distinct rows, so these are $N$ distinct queens. Labeling the prescribed queens does not lose a board completion: the queens are physically indistinguishable, and any completion can be labeled to give the prescribed ones those indices. It does create redundant assignments for the remaining labels.

Model 3: one variable per row. Let $C_r\in \{1,\dots ,N\}$ be the queen’s column in row $r$. For every $r<s$, requireand impose $C_r=c$ for every $(r,c)\in F$. These restrictions give $N$ queens, one per row; the all-different constraint on the columns gives one per column. For $N$ nonattacking queens on $N$ rows, exactly one per row is forced by the pigeonhole principle, so no solutions are lost. Inconsistent prescribed positions in a single row give incompatible unary restrictions. All three are exact constraint satisfaction problem encodings of the queens completion problem.