The generalized pigeonhole principle
At least how many students in our class were born on the same day of
The generalized pigeonhole principle: If N objects are placed into k
boxes, then there is at least one box containing at least ?N/k? objects.
Proof: Suppose none of the boxes contains ?N/k? or more objects.
Then every box contains at most ?N/k? -1 objects.
So, the total number of objects is at most k(?N/k? -1 ).
Thus, the total number of objects is less than k(N/k),
This is a contradiction. End of proof.
How many students should be in our class to guarantee that at least
4 of them were born on the same day of the week?
?N/7? should be at least 4.
So, N should be 22 or more.