4
$\begingroup$

If $n$ people are placed in a room, then at least $2$ of those people will have the same number of friends in the room.

I want to prove this statement.

Here are some of my thoughts:

  1. If all the people are strangers, then clearly everyone has zero friends in the room. Hence they all have the same number of friends. Thus, clearly there exists at least one pair in the room with the same number of friends. I see this as the trivial case.

  2. Maybe I can prove this by assuming that, for any collection of $n$ people, all the people have a different number of friends; perhaps I can then find a contradiction.

Proceeding with the idea in 2., I devised the following relationship:

person $1$ has $0$ friends, person $2$ has $1$ friend, person $3$ has $2$ friends, ... , person $(n-1)$ has $(n-2)$ friends, person $n$ has $(n-1)$ friends

Now I want to find a way to use this relationship to show that a contradiction arises, i.e. at least $2$ people must have the same number of friends in the room.

$\endgroup$
2
  • 4
    $\begingroup$ If I was in a room with iron man I would think I have one friend in the room, Iron man would not think the same. $\endgroup$
    – Asinomás
    Jul 13, 2015 at 16:03
  • $\begingroup$ Funny, but consider the following: friendship is not reflexive or transitive, for the purpose of this problem; however, friendship is symmetric. $\endgroup$
    – idkmybffjill
    Jul 13, 2015 at 16:25

4 Answers 4

Reset to default
7
$\begingroup$

Hint: what are the possible number of friends in the room each person can have?

Full solution:

The number of friends possible is $n$, they are $0,1,2\dots n-1$. However if there is a person $A$ with $0$ friends then there can't be a person $B$ with $n-1$ friends, since for that to happen $A$ would have to be a friend of $B$, but $A$ has no friends. Therefore at most $n-1$ values for the number of friends in the room. There are $n$ persons, so by the pigeonhole principle at least two people must have the same number of friends.

$\endgroup$
6
$\begingroup$

Assuming that the friend relation is symmetric, you can't have both a person with $0$ friends and a person with $n-1$ friends, since the $n-1$-friend person has to be friends with everyone else in the room, including the person who is supposed to have $0$ friends.

$\endgroup$
3
$\begingroup$

Hint: Draw a graph whose vertices correspond to the people in a room, and whose edges correspond to friendship between two people. The question is now reduced to showing that there exist two vertices of the same degree in a graph on at least two vertices. See here for more information:

http://puzzlesland.com/mathprob/graph-samedeg.html

$\endgroup$
1
$\begingroup$

Hint: Pigeonhole principle.

Argue why if you divide up your persons into a relation you mentioned why it is not possible to have a person having n friends (using injectivity of $f: {persons} \rightarrow$ {#friends of person p})

There is a second case: person #1 has 1 friend, ..., person #n has n friends. Handle that in a similar manner.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .