if objects are distributed into boxes then at least one box contains two or more of the objects
Example
Let be integers
then with such that is divisible by
if any of the is divisible by m we are done as and
Else from pigeonhole principle we know at least two of will have same residue say
then
Theorem(Dirichlet).
let and be a real number then there exist integers and with S.T.
Theorem(Strong form of Pigeonhole principle).
let be positive integers. If boxes are distributed into n boxes then,
either box contains at least objects,
or the box contains at least objects,
so on,
or the box contains at least objects
Proof.
If the box contains less than objects then the boxes can at most contain objects □