Pigeonhole Principle

Pigeonhole Principle states

           “If n+1 objects are put into n boxes, then at least one box contains two or more objects .”
i.e. n+1 objects = pigeon

n boxes = pigeonholes

Applications

1. Among 13 people there are two who have their birthdays in the same month.
2. Given m integers a₁,a₂,…..,a_m  there exist k and l with 1≤k≤l≤m such that a_k+1+a_k+2+_….+a_l  is divisible by m. Less formally, there exist consecutive a’s in the sequence a1,a2,…..,am whose sum is divisible by m.

Strong Form of Pigeonhole Principle
Let q_1,q₂,….,q_n be positive integers. If q₁+q₂+…+q_n-n+1 objects are put into n boxes, then either the first box contains at least q₁ objects, or the second box contains at least q₂ objects,…. or the nth box contains at least qn objects.