Results 1 to 3 of 3

Math Help - pigeon hole principle

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    6

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by dbhakta View Post
    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.
    Last edited by awkward; April 15th 2008 at 08:03 PM. Reason: added more excellent advice
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    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)} .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 04:24 AM
  2. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 07:22 PM
  3. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 02:56 AM
  4. Pigeon Hole Principle Help!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 16th 2008, 11:14 PM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 05:37 PM

Search Tags


/mathhelpforum @mathhelpforum