Results 1 to 5 of 5

Thread: Pigeonhole Principle Problem

  1. #1
    Super Member
    Joined
    Jul 2015
    From
    United States
    Posts
    519
    Thanks
    10

    Pigeonhole Principle Problem

    There are two people on facebook with same number of friends.

    So we let X= set with at least 2 people.
    Let Y= Possible number of friends, person in X can have.

    Y is a subset {0,1,2,...,n-1}
    define f:X->Y,

    where f(x) = number of friends X has. (WTS: | Y | is less than or equal to n.

    so f(x_0)=0 for some x_0 in x means someone has no friends.
    Then this means, no one can have n-1 friends, (i.e. friends with everyone else). I am stuck here and not sure where to go.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,170
    Thanks
    49

    Re: Pigeonhole Principle Problem

    I'm struggling with where you started and where you intend to go. Is there a problem statement or definition? How do you know we'll need the PHP?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2012
    From
    Normal, IL USA
    Posts
    197
    Thanks
    29

    Re: Pigeonhole Principle Problem

    Thanks to TKHunny for asking that. I think some of us, including me, are in the "emperor no clothes" situation. We don't want to admit that we don't understand the OP's question.

    I'm going to go out a limb. I think the OP wants to prove that no matter what, there must be at least two distinct people on FB who have the same number of friends. That sounds like the kind of thing you'd prove with the PHP, and that you'd get as a question in a discrete math class.

    I'm rusty on the PHP. I'll go take another look at it. If I'm right though, somebody will solve this very soon.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,170
    Thanks
    49

    Re: Pigeonhole Principle Problem

    Are we to assume that there are at least two people on Facebook?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    1,039
    Thanks
    530

    Re: Pigeonhole Principle Problem

    if card $(X)>$ card $(Y)$ then $f$ cannot be injective

    therefore there exist $x,y$ such that $x \neq y$ and $f(x)=f(y)$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 20th 2011, 03:46 PM
  2. Replies: 2
    Last Post: Aug 28th 2011, 02:19 AM
  3. Replies: 2
    Last Post: Aug 27th 2011, 08:26 AM
  4. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 31st 2009, 03:58 PM
  5. Pigeonhole principle?
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: Dec 9th 2007, 08:58 AM

/mathhelpforum @mathhelpforum