The basic version of the pigeonhole principle
The pigeonhole principle: If k+1 or more objects are placed into k
boxes, then there is at least one box containing two or more of the objects.
Proof: Suppose none of the k boxes contains more than one object.
Then the total number of objects would be at most k. This is a
contradiction, because we have more than k objects.
Example 1: Among 367 people, there must be at least two with the
BTW, what if there are 368 people?
Example 2: How many students must be in our class to guarantee that
at least two of them receive the same score on the final exam?
Answer: Since there 101 possible scores, the class should have at least