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. Example 1: If there are 11 players in a soccer team that wins 12-0, there must be at least one player in the team who scored at least twice. Example 2: If you have 6 classes from Monday to Friday, there must be at least one day on which you have at least two classes.

The Pigeonhole Principle
The generalized pigeonhole principle: If N objects are placed into k boxes, then there is at least one box containing at least [N/kl of the objects.
Example 1: In our 60-student class, at least 12 students will get the same letter grade (A, B, C, 0, or F).

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.
If N objects are placed into k b oxes, then there is at least one box containing at least [N/kl of the objects.

Proposition PHP1. (The Pigeonhole Principle, simple version.) If k+1 or more pigeons are distributed among k pigeonholes, then at least one pigeonhole contains two or more pigeons. Proof. The contrapositive of the statement is: If each pigeonhole contains at most one pigeon, then there are at most k pigeons. This is easily seen to be true. The same argument can be used to prove a variety of different statements. We prove the general version of the Pigeonhole Principle and leave the others as exercises.
Proposition
PHP2. (The Pigeonhole Principle.) If n or more pigeons are distributed among k > 0 pigeonholes, then at least one pigeonhole contains at least n k pigeons. Proof. Suppose each pigeonhole contains at most n k − 1 pigeons. Then, the total number of pigeons is at most k( n k − 1) < k( n k ) = n pigeons (because n k − 1 < n k ≤ n k ). Exe