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.