1st principle of Pigeonhole
• Imagine 9 pigeonholes and 10 pigeons. A storm comes along, and all of the pigeons take shelter inside the pigeonholes.
• They could be arranged any number of ways. For instance, all 10 pigeons could be inside one hole, and the rest of the holes could be empty.
• What we know for sure, no matter what, is that there is at least one hole that contains more than one pigeon.
The principle works no matter what the particular number of pigeons and pigeonholes. As long as there are (N - 1) number of pigeonholes, and (N) number of pigeons, we know there will always be at least two pigeons in one hole.
3rd principle of Pigeonhole
2nd principle of Pigeonhole
If f is a function from a finite set X to a finite set Y and |X| > |Y|, then f(x1)= f(x2) for some x1,x2 ∈ X, x1≠ x2
The 2nd form can be reduced to the 1st form by letting X be the set of pigeons and Y be the set of pigeonholes.
Assign pigeon x to pigeonhole f(x)
Let= {1,2,3,4,5,6}. Show that if we choose any four distinct members of A, then for at least one pair of these four integers their sum is 7. • Notice that {1,6}, {2,5} and {3,4} are the only pairs of distinct integers such that their sum is 7. • Let= ,,, be any subset of four distinct elements of A. • Let= { 1,6 , 2,5 , 3,4 }, a set of 3 distinct elements and a part of A. = 1,6 ,= 2,5 ,= {3,4}