0

$X$ is a group of persons and $\vert X \vert \geq 2 $. Every person in $X$ has a certain amount of friends in $X$. The friendship relation is symetric. Prove that there are two persons in $X$ with the same amount of friends in $X$.

I was thinking to prove this with induction but i'm struggling a bit, can someone help?

I started proving it for a group of size 2 this was not hard. After this I said the proposition is correct for a group of size $n$. Than i tried proving the proposition was correct for a group of size $n+1$, therefore I tried just adding a person to the group of $n$ people and distinguising the different cases:

  • case 1:the new person is friends with one of two in the old couple with the same amount of friends and

  • case 2: the person is not friends with one of the couple with the same amount of friends (than the couple is stil the same one so no problem)

For case 1 i thought about removing someone who doesn't matter for the situation so that there is a group of $n$ people again but here I started struggling.

Mich Vaughan
  • 99

2 Answers2

1

Suppose there is a person with 0 friends, and another one which is friend with everyone else. These two contradict each other, so either no one has zero friends, or no one is friends with everyone else.

This leaves for the possible amounts of friends less options that people in the set, and by the pigeonhole principle two people must have the same number of friends.

rewritten
  • 3,092
  • "Suppose there is a person with 0 friends, and another one which is friend with everyone else. These two contradict each other..." Explain. – David G. Stork Jul 28 '22 at 18:59
  • 3
    The person who is friends with everyone else must in particular be friends with the person with 0 friends. Since friendship is symmetric, the person with 0 friends is friends with this person too, which is a contradiction. – Xavi Jul 28 '22 at 19:01
0

We create the following n-1 pigeonholes: (1),(2),,,,,,(n-2) and (0, n-1) that is we put the 0 and n-1 in the same pigeonhole since as it was mentioned above the combination of O and n-1 freindships are incompatible Since there are n persons and n-1 pigeonholes there must be at least one pigeonhole with at leat 2 persons in it

koke
  • 41