If
one distributes k pigeons to n
pigeonholes and k > n
, then certainly some pigeonhole must hold more than one pigeon.
Alternatively
Let A and B be
sets of 'k 'and ' n
' elements respectively. Let f be a function from A to B. If k
> n, then there are at least two elements
x, y 
A , such
that x
y and f(x)=f(y)
Example:
In a group of 13 people there must be atleast two
who were born in the same month? Why?
|
In this situation think of the people as the pigeons
and the months as the pigeonholes.
We have here 13 pigeons, but only 12 pigeonholes, as there are 12 months to a year. We can have a situation here, where 12 people(pigeons) belong to 12 different months(pigeonholes) of the year, but the 13th person has to belong to one of the 12 months too, so this leaves us with atleast one person belonging to a month (pigeonhole), which is already filled by a person(pigeon). |
 |
 |
The Extended PigeonHole Principle
If there are m pigeonholes and more
than 2m pigeons , then three or more
pigeons will have to be assigned to
at least one pigeonhole.
If
n pigeons are assigned to m pigeonholes, then one
of the pigeonholes must contain at least
[ (n-1) / m ] + 1 pigeons.
Proof:
If each pigeonhole contains no more than [ (n-1)/ m] pigeons,
then there are at least
m*[ (n-1) / m] <= m * (n - 1 ) / m
= n - 1 pigeons in all.
The
above contradicts our assumptions, so one of the pigeonholes must contain
at least
[ (n - 1)/ m] + 1 pigeons.
Example:
|
If 71 letters are distributed to 70 mailboxes,
then atleast one mailbox must contain at least 2 letters.If 71 letters
are distributed
|
|
|
