# pigeon hole principle

• April 15th 2008, 06:03 PM
dbhakta
pigeon hole principle
if A and B are finite sets with |B|=n and |A| >= kn + 1 where k and n are positive integers and f:A--->B, then there exists a b within B such that |f^-1(b)| >= k+1.

Does anyone know how to prove this?
• April 15th 2008, 07:53 PM
awkward
Quote:

Originally Posted by dbhakta
if A and B are finite sets with |B|=n and |A| >= kn + 1 where k and n are positive integers and f:A--->B, then there exists a b within B such that |f^-1(b)| >= k+1.

Does anyone know how to prove this?

Hint: Use an indirect proof. Assume the contrary and arrive at a contradiction.

Edit: It may also help to think of the problem in more concrete terms. (All this inverse function stuff gives me a headache.) Rephrase the problem: If more than kn objects are placed in n pigeonholes, then some pigeonhole contains more than k objects.
• April 16th 2008, 03:39 AM
Plato
Suppose that $\left( {\forall b \in B} \right)\left[ {\left| {f^{ - 1} (b)} \right| < K + 1} \right]$.
Recall that $A = \bigcup\limits_{b \in B} {f^{ - 1} (b)}$.