This
principle was first stated by
Dirichlet in 1834 and has
important applications in
number theory.
If m pigeons are put into m pigeonholes, there is an empty hole if and only if there's a hole with more than one pigeon.
It is also known as the
Dirichlet's Box Principle, which reads:
If n>m pigeons are put into m pigeonholes, there's a hole with more than one pigeon.
Here's a simple
application: if we have 37 students in our
classroom, then at least 4
students must have their birthdays in the same month. (The pigeonholes are the months, so n = 12; clearly 37 = 12ยท3 + 1 so r = 3.)
A similar
principle to the
Pigeonhole Principle is the
Fubini Principle:
If the average number of envelopes per pigeonhole is a, then some pigeonhole will have at least a envelopes. Similarly, there must be a pigeonhole with at most a envelopes.