Results 1 to 2 of 2

Math Help - generalised pigeonhole principle

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    12

    Thumbs up generalised pigeonhole principle

    Hello,

    The generalised pigeonhole principle is proved by using contradiction. The proof is given below.

    consider there are no pigeonholes that contain more than ceil(m/n) - 1.

    Then the total number of pigeons m <= n * ceil(m/n)-1
    m < n*(m/n) + 1 - 1
    m = m which is a contradiction.


    Can anyone please tell how it is a contradiction.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by sudeepmansh View Post
    Hello,

    The generalised pigeonhole principle is proved by using contradiction. The proof is given below.

    consider there are no pigeonholes that contain more than ceil(m/n) - 1.

    Then the total number of pigeons m <= n * ceil(m/n)-1
    m < n*(m/n) + 1 - 1
    m = m which is a contradiction.


    Can anyone please tell how it is a contradiction.
    I think there is an error in what you wrote.

    "m = m which is a contradiction"

    it has to be m < m which is a contradiction. This follows directly from the preceding step.
    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 #3
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 06:38 PM
  3. Pigeonhole principle?
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: December 9th 2007, 08:58 AM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum