Discrete Mathematical Structures by Pearson

Combinatorics 5-17

Similarly, no function {1, 2, 3, 4} → {x, y} can be one to one. The statement that no function

is one to one essentially means that if B is a set of bird houses and A is a set of pigeons, then the

function f will assign at least two pigeons to the same house.

The pigeonhole principle is quite helpful in proving interesting results.

Example 1 Let 8 persons be selected at random from any group, then at least two of them will

have been born on the same day of the week.

Solution: Consider the days of the week as pigeonholes and the birthdays of 8 persons as

the pigeons. Thus, there are 8 pigeons and 7 pigeonholes. Hence, according to the pigeonhole

principle at least two persons will have the same day of their birth.

Example 2 ...