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 a1,a2,…..,am  there exist k and l with 1≤k≤l≤m such that ak+1+ak+2+….+al  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 q1,q2,….,qn be positive integers. If q1+q2+…+qn-n+1 objects are put into n boxes, then either the first box contains at least q1 objects, or the second box contains at least q2 objects,…. or the nth box contains at least qn objects.

Leave a Reply

Your email address will not be published. Required fields are marked *