Definition
Pigeonhole Principle
Given two sets
and with , then a relation cannot be injective, meaning: In other words, since
, one cannot map a bigger set into a smaller set while preserving injectivity.
Generalisation
Definition
Link to originalGeneralised Pigeonhole Principle
Let
be a finite set of objects and let . If a function assigns every object to one of bins, define the load of bin by Since every object is assigned to exactly one bin,
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:
The two bins need not be the same.