Results 1 to 9 of 9

Math Help - PigeonHole Principle

  1. #1
    Junior Member
    Joined
    Apr 2011
    Posts
    30

    PigeonHole Principle

    Show that in any set of n integers, n>= 3, there always exists a pair of integers
    whose di erence is divisible by n - 1. (Use the pigeonhole principle.)


    I can never seem to figure out how to do these pigionhole principle problems. Every one of them seems different to the last one I looked at. Is there some kind of process to it? How would you do the one above?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1

    Re: PigeonHole Principle

    Quote Originally Posted by nukenuts View Post
    Show that in any set of n integers, n>= 3, there always exists a pair of integers
    whose di erence is divisible by n - 1. (Use the pigeonhole principle.
    The key to understanding this is: If (all of these are positive integers) a~\&~b have the same remainder when divided by k then b-a is divisible by k.

    The only remainders when dividing by n-1 are \{0,1,\cdots,n-2\} those are the pigeonholes and the n integers are the pigeons.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2011
    Posts
    30

    Re: PigeonHole Principle

    OK what about this one-
    Show that in any set X of two or more people, there are two people who have
    the same number of friends in X. (Use the pigeonhole principle.)

    I can see that this is the case if I write out several sample sets. I figure the people are the pigeons and the number of friends are the holes. But I dont know how to write this down mathematically?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Apr 2011
    Posts
    30

    Re: PigeonHole Principle

    What about
    The amount of possible friends for each person in the set X will be between 0 and X-1...Actually wont work because there are X pigeon (people) in the set X, and there are also X holes (number of friends) in the set 0 - X-1.

    So if X is 3
    Each person could either have 0, 1 or 2 friends. So 3 pigeons into 3 holes...that is not going to work.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: PigeonHole Principle

    Quote Originally Posted by nukenuts View Post
    So if X is 3
    Each person could either have 0, 1 or 2 friends. So 3 pigeons into 3 holes...that is not going to work.
    But if someone has 2 friends, this involves all people in the group, so no person can have 0 friends (presumably, friendship is symmetric).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Apr 2011
    Posts
    30

    Re: PigeonHole Principle

    OK, but would I write that down in a mathematical form? And I need to write it so that it holds for all X, not just X = 3... I just cant see how to write an answer.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: PigeonHole Principle

    Quote Originally Posted by nukenuts View Post
    OK, but would I write that down in a mathematical form?
    I hope you would.

    Quote Originally Posted by nukenuts View Post
    And I need to write it so that it holds for all X, not just X = 3... I just cant see how to write an answer.
    Consider the same situation for a group of 4 people and try to extend the reasoning from the case of 3 and 4 to n.

    You are considering functions from {1, ..., |X|} to {0, ..., |X| - 1} that map people to the number of their friends. You can show that |X| - 1 or 0 is not in the range of such function. This makes pigeonhole principle applicable: the set of pigeons is the domain and the set of holes is the range. More formally, pigeonhole principle says that any function with domain A and range B where |A| > |B| cannot be an injection, and this is precisely the situation that you have here.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Apr 2011
    Posts
    30

    Re: PigeonHole Principle

    Quote Originally Posted by emakarov View Post
    I hope you would.

    Consider the same situation for a group of 4 people and try to extend the reasoning from the case of 3 and 4 to n.

    You are considering functions from {1, ..., |X|} to {0, ..., |X| - 1} that map people to the number of their friends. You can show that |X| - 1 or 0 is not in the range of such function. This makes pigeonhole principle applicable: the set of pigeons is the domain and the set of holes is the range. More formally, pigeonhole principle says that any function with domain A and range B where |A| > |B| cannot be an injection, and this is precisely the situation that you have here.
    Cheers for showing me the proper way to view it mate. Ok so I have the two ranges {1, ..., |X|} to {0, ..., |X| - 1} that map people to the number of friends.

    If a person has |X| - 1 friends that means they are friends with everyone else in the group, hence nobody will have 0 friends so the range of friendships will be 1 to |X| - 1.

    If a person has 0 friends that means there will be nobody in the group who will be be friends with everybody else (nobody will have |X| - 1 friends), so the range will be from 0 to |X| - 2.

    In either of these cases the number of possible friendships is |X|-1. Generally, the range of number for friendships will always be of size |X|-1. So putting |X| pigeons into |X|-1 holes means that at least hole will contain more than two items.

    Is that a decent way of answering it or is it a bit messy?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: PigeonHole Principle

    Quote Originally Posted by nukenuts View Post
    Ok so I have the two ranges {1, ..., |X|} to {0, ..., |X| - 1} that map people to the number of friends.
    The word "range" has a specific meaning with respect to functions.

    The set of all inputs to a particular function is called its domain. The set of all outputs of a particular function is called its image. In modern mathematics functions also have a codomain. For every function, its codomain includes its image... The word range is used in some texts to refer to the image and in others to the codomain, in particular in computing it often refers to the codomain. (Wikipedia)
    I should have used the word "image" in post #7. So, {1, ..., |X|} is the domain and {0, ..., |X| - 1} is the codomain, but the actual image is smaller than the codomain because it does not include 0 or |X| - 1 (or both).

    Quote Originally Posted by nukenuts View Post
    If a person has |X| - 1 friends that means they are friends with everyone else in the group, hence nobody will have 0 friends so the range of friendships will be 1 to |X| - 1.

    If a person has 0 friends that means there will be nobody in the group who will be be friends with everybody else (nobody will have |X| - 1 friends), so the range will be from 0 to |X| - 2.

    In either of these cases the number of possible friendships is |X|-1.
    And, of course, the same conclusion holds when there are no people with 0 or |X| - 1 friends to begin with.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 14th 2010, 02:12 PM
  2. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 04:59 PM
  3. Pigeonhole principle?
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: December 9th 2007, 09:58 AM
  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