Results 1 to 3 of 3

Math Help - Pigeonhole Principle

  1. #1
    Member
    Joined
    Aug 2007
    Posts
    239

    Pigeonhole Principle

    How many proofs are there for the pigeonhole principle? I know of one proof that just uses composition of functions to develop lemmas, and then ultimately come up with the Pigeonhole principle. The proof starts with the basic problem of 2 different ways of counting sets (i.e if  f: \mathbb{N}_{m} \to X and  f: \mathbb{N}_{n} \to X are bijections with the same codomain, then  m = n ). Namely, it says the following: Suppose that  X and  Y are finite, non-empty sets such that  |X| > |Y|. Then  f: X \to Y is not an injection.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    What is a finite set? It is a set such has no proper subset has a bijection with the full set. Use that fact and prove formally the principle.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    There are several proofs as you observe. This of is found in many discrete mathematics texts.
    Given that m = \left| X \right| > \left| Y \right| = n, recall that <br />
X = \bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}} .

    Suppose that \left( {\forall y \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ y \right\}} \right| \le 1} \right]\quad.

    Using that we have \left| X \right| = \left| {\bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}} } \right| = \bigcup\limits_{y \in Y} {\left| {\overleftarrow f \left\{ y \right\}} \right|}  \le n that is a contradiction.
    Thus \left( {\exists z \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ z \right\}} \right| > 1} \right].

    The value of this proof is that it also proves the generalized form. If we have m pigeons and n pigeonholes with m > n the some hole contains at least \left\lceil {\frac{m}{n}} \right\rceil pigeons (that is the ceiling function).

    To see this proof use the assumptions above, using the supposition that k = \left\lceil {\frac{m}{n}} \right\rceil \quad \& \quad \left( {\forall y \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ y \right\}} \right| < k} \right].

    This time \left| X \right| = \left| {\bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}} } \right| = \bigcup\limits_{y \in Y} {\left| {\overleftarrow f \left\{ y \right\}} \right|}  \le n\left( {k - 1} \right) \le m that is a contradiction.
    Thus \left( {\exists z \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ z \right\}} \right| \ge k} \right].
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  4. Pigeonhole principle?
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: December 9th 2007, 08:58 AM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum