Results 1 to 10 of 10

Math Help - Pigeonhole Principle

  1. #1
    Junior Member
    Joined
    Jun 2007
    Posts
    40

    Pigeonhole Principle

    Let d be a positive integer. Show that among any group of d +1 (not necessary consecutive) integers, there are two with exactly the same remainder when divided by d.
    Last edited by Discrete; July 22nd 2007 at 08:00 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Discrete View Post
    Let d be a positive integer. Show that among any group of d +1 (not necessary consecutive) integers, there are two with the same remainder when divided by 4.
    i believe there is something missing from the question, or you're not describing something correctly. one thing i can see (i may be wrong) we have to have that d \geq 4, otherwise, we cannot show what we are being asked.

    for the sake of illustration, let's say d = 1, that is a positive integer. so d + 1 would be 2. there is no guarantee, by the pigeonhole principle or otherwise, that any arbitrary group of two integers would have two elements that are congruent mod 4
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Are you sure your problem isn't 'd' instead of 4?.

    "Let d be a positive integer. Show that among any group of d+1 (not necessary consecutive) integers, there are two with the same remainder when divided by d".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Given n+1 integers which are the "pigeons". Let the sets \{0\} , \{1\}, ... ,\{n-1\} be the remainders upon division by n. Since there are n holes and n+1 pigeons we conclude that two have the same remainder.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2007
    Posts
    40
    Sorry guys I revised the question, there are some typo's there it should be divided by d
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Discrete View Post
    Sorry guys I revised the question, there are some typo's there it should be divided by d
    Yes, TPH's solution is valid for the revised question. he (and galactus) read through the lines and figured that's what you were really asking
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2007
    Posts
    40
    Quote Originally Posted by Jhevon View Post
    Yes, TPH's solution is valid for the revised question. he (and galactus) read through the lines and figured that's what you were really asking

    I still don't get what TPH is saying, is the set {0}, {1}, ... {n-1} the remainder? if yes then where is the same remainder?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Discrete View Post
    I still don't get what TPH is saying, is the set {0}, {1}, ... {n-1} the remainder? if yes then where is the same remainder?
    when you divide an integer by some other integer, the remainder can range from zero right up to 1 less than the number you divided by: if you divide by 4, the possible remainders are 0, 1, 2 and 3. If you divide by 2, the possible remainders are 0 and 1, if you divide by 5, the possible remainders are 0,1,2,3, and 4. if you go any greater than this, you repeat this cycle. let's say you could have more remainders than this. let's say if you divide by 2, your possible remainders could be 0,1, and 2. 0 and 1 are fine, but if the remainder is 2, you could simply get another factor of 2 out of the original number and have a remainder of zero.

    TPH used that principle. We have n + 1 integers being divided by n, so the possible remainders are 0, 1, 2, 3, ..., (n - 1), one less than the number we divided by. if you count starting from 0 up to (n - 1) you get n remainders. look at my illustrations above, you will find if you divide by 2 you have 2 possible remainders, if you divide by 5, you have 5 possible remainders. so here, we have n possible remainders. but there are (n + 1) integers, meaning when you get to the nth integer, you would have exhausted the n remainders, so the next (n + 1)th integer must reuse one of the remainders already used, so there will be two numbers with the same remainder when divided by n

    see here for more on the Pigeonhole Principle
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jun 2007
    Posts
    40
    gotcha jhevon's, I got it a bit more clear now.. so the remainder here can be represented as the pigeons right? and n+1 is the hole/cage of the pigeon?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Discrete View Post
    gotcha jhevon's, I got it a bit more clear now.. so the remainder here can be represented as the pigeons right? and n+1 is the hole/cage of the pigeon?
    no, the remainders are the holes, and the integers are the pigeons

    if you pick an integer and it has a remainder of 0 when divided by n, then you put it in the hole for 0, if it has a remainder of 1 when divided by n, you put it in the hole for 1, and so on. eventually, after n consecutive integers, you would have filled all the holes, and the last integer must be put into a hole that is already used. (if the integers are not necessarily consecutive, and it is the case that you haven't filled the holes by the nth integer, it simply means you already reused one of the holes at least once, so there are already at least two integers with exactly the same remainder)
    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: November 1st 2009, 12:23 AM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 04:58 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 04:59 PM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 04:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 07:09 PM

Search Tags


/mathhelpforum @mathhelpforum