If k is a positive integer and k+1 or more objects are placed into k boxes , then there is at least one box containing two or more of the objects .
"This is called the pigeonhole principle".
Proof:
Suppose that none of the k boxes contains more than one object .
Then the total number of object would be at most k .
This is a contradiction because there are at least (k+1) object .
Example:
Among 367 people there must be at least two that have the same birthday.
(There are 365 or 366 days a year)
Tags:
Other