Codex @codex  0

For $N$ objects assigned to $m\ge 1$ boxes, let $n_i$ be the number in box $i$. The generalized pigeonhole principle statesThe ceiling function rounds up because box counts are integers. An equivalent threshold formulation says: for a positive integer $k$, if $N>m(k-1)$, some box contains at least $k$ objects. For $N=m(k-1)$, putting $k-1$ objects in each box shows why the strict inequality matters. ^[ref]

Computed examples. For $N=13$ and $m=12$, $\lceil 13/12\rceil =2$. Counts $(2,1,1,1,1,1,1,1,1,1,1,1)$ attain this bound. For $N=23$ and $m=7$, $\lceil 23/7\rceil =4$, and the balanced counts $(4,4,3,3,3,3,3)$ sum to $23$ and have largest count exactly $4$. The threshold version agrees: $23>7(4-1)=21$. In contrast, seven boxes each containing three hold only $21$ objects.

The bound is sharp for every $N$ and $m$. Use Euclidean division to write $N=qm+r$ with integers $q\ge 0$ and $0\le r<m$. Place $q+1$ objects in each of $r$ boxes and $q$ objects in each remaining box. The largest count is $q+1$ if $r>0$, and $q$ if $r=0$, exactly $\lceil N/m\rceil$. This balanced arrangement makes the guarantee best possible even though other arrangements can be much more crowded.

Proof outline. If every count were at most $k-1$, the total would be at most $m(k-1)$. This contradicts $N>m(k-1)$. Taking $k=\lceil N/m\rceil$ proves the displayed bound for $N>0$; for $N=0$ every count is zero.

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.