Generalised Pigeonhole Principle

Definition

Generalised Pigeonhole Principle

Let $A$ be a finite set of $N$ objects and let $k\ge 1$. If a function $f:A\to \{1,\dots ,k\}$ assigns every object to one of $k$ bins, define the load of bin $j$ by

$${\ell }_j:=|f^{-1}(j)|.$$

Since every object is assigned to exactly one bin,

$$\sum _{j=1}^k{\ell }_j=N.$$

Therefore at least one bin contains at most the floor of the average load, and at least one bin contains at least the ceiling of the average load:

$$\exists i,j\in \{1,\dots ,k\}:{\ell }_i\le \lfloor \frac{N}{k}\rfloor \text{and}{\ell }_j\ge \lceil \frac{N}{k}\rceil .$$

The two bins need not be the same.

Proof

Generalised Pigeonhole Principle

Let

$$m:=\underset{1\le j\le k}{\min }{\ell }_j\text{and}M:=\underset{1\le j\le k}{\max }{\ell }_j.$$

Every load lies between these extremes, so $m\le {\ell }_j\le M$ for every $j$. Summing these inequalities gives

$$km\le \sum _{j=1}^k{\ell }_j=N\le kM.$$

Dividing by $k$ establishes the relation between the minimum, the average, and the maximum load:

$$m\le \underset{\text{average load}}{\underbrace{\frac{N}{k}}}\le M.$$

Since $m$ and $M$ are integers, the left inequality gives $m\le \lfloor N/k\rfloor$, while the right inequality gives $M\ge \lceil N/k\rceil$. Thus a bin attaining $m$ has at most $\lfloor N/k\rfloor$ objects, and a bin attaining $M$ has at least $\lceil N/k\rceil$ objects.

Average and Extremes

The principle is an integer version of the general fact that an average cannot lie outside the range of the values being averaged:

$$\underset{\text{smallest load}}{\underbrace{\underset{1\le j\le k}{\min }{\ell }_j}}\le \underset{\text{average load}}{\underbrace{\frac{1}{k}\sum _{j=1}^k{\ell }_j}}\le \underset{\text{largest load}}{\underbrace{\underset{1\le j\le k}{\max }{\ell }_j}}.$$

Consequently:

• a lower bound on the average gives a lower bound on the maximum load;
• an upper bound on the average gives an upper bound on the minimum load.

The floor and ceiling appear because loads are whole numbers. The average itself need not be an integer, but every load is.

The ordinary pigeonhole principle is the special case in which $N>k$. Then

$$\lceil \frac{N}{k}\rceil \ge 2,$$

so some bin contains at least two objects. Two objects in the same bin are precisely a collision under the assignment function $f$.

Examples

Eleven objects in three bins

Suppose the loads are $(5,4,2)$. Their average is

$$\frac{5+4+2}{3}=\frac{11}{3}.$$

The largest load is $5\ge \lceil 11/3\rceil =4$, and the smallest load is $2\le \lfloor 11/3\rfloor =3$. The theorem does not predict which bins have these loads; it guarantees only that both kinds of bin exist.