THE PIGEON HOLE PRINCIPLE

BLOG CREDITS VIVEK FIRST-YEAR CSE

:-Statement:-If we put more than n pigeons into n pigeonholes, at least one pigeonhole will house two or more pigeons.Form1:-If m objects are put in n boxes and n < m, then at least one box contains at least two objects. The one-line proof is by contradiction: If every box contains at most one object, there are at most n · 1 = n objects. A more rigorous formulation of the principle is as follows: Given two sets A and B, with |A| = m > n = |B|, for any function, f : A → B there exists b ∈ B such that |{x ∈ A: f(x) = b}| > 1.Form 2:-For a nonempty finite collection of integers (not necessarily distinct), the maximum value is at least the average value.Form:-3 If m objects are put in n boxes, then at least one box contains at least ¢[m/n] objects. The proof is again by contradiction: If every box contains at most ¢[m/n] − 1 < m/n objects, there are less than n(m/n) = m objects.(Where ¢[k] is ceiling function of k)Example:- A bag contains 5 red, 8 blue, 12 green, and 7 yellow marbles. The least number of marbles to be chosen to ensure that there are

(a) at least 4 marbles of the same color are 13

(b) at least 7 marbles of the same color is 24,

(c) at least 4 red or at least 7 of any other color is 22.