# Thread: Pigeonhole Principle Problem

1. ## 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.

2. ## 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?

3. ## 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.

4. ## Re: Pigeonhole Principle Problem

Are we to assume that there are at least two people on Facebook?

5. ## 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)$