THE PIGEONHOLE PRINCIPLE (FUNCTIONS)

THE PIGEONHOLE PRINCIPLE

A function from one finite set to a smaller finite set cannot be one-to-one: There must be at least two elements in the domain that have the same image in the co-domain.

THE GENERALIZED PIGEONHOLE PRINCIPLE

For any function f from a finite set X to a finite set Y and for any positive integer k, if n(X) > k[n(Y)], then there is some y Î Y such that y is the image of at least k + 1 distinct elements of X.

THE GENERALIZED PIGEONHOLE PRINCIPLE (CONTRAPOSITIVE FORM)

For any function f from a finite set X to a finite set Y and for any positive integer k, if for each y Î Y,

f^-1(y) has at most k elements, then X has at most

k[n(Y)] elements.

THEOREM:

If m = m₁ + m₂ + m₃ + … + m_n – n + 1 pigeons are placed in n pigeonholes, where m_i is a positive integer for each 1 £ i £ n, then for some i, the ith pigeonhole contains at least m_i pigeons.

Proof: by contradiction.