Track / Stage 7 / 203 of 300 #1603 of 1964

Problem 1603

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.4 Prove it

There are $n\geq 2$ people at a meeting. Show that there exist two people at the meeting who have the same number of friends among the persons at the meeting. (It is assumed that if $A$ is a friend of $B,$ then $B$ is a friend of $A;$ moreover, nobody is his own friend.)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Assume for contradiction: Suppose that all $n$ people at the meeting have distinct numbers of friends. This means that each person has a unique number of friends ranging from $0$ to $n-1$ .

2. Range of possible friends: The number of friends a person can have ranges from $0$ to $n-1$ . Therefore, if each person has a distinct number of friends, there must be exactly one person with $0$ friends, one person with $1$ friend, one person with $2$ friends, and so on, up to one person with $n-1$ friends.

3. Contradiction: Consider the person who has $0$ friends. This person is not friends with anyone else. Now consider the person who has $n-1$ friends. This person must be friends with every other person at the meeting, including the person who has $0$ friends. This is a contradiction because the person with $0$ friends cannot be friends with anyone, including the person with $n-1$ friends.

4. Conclusion: Since assuming that all $n$ people have distinct numbers of friends leads to a contradiction, it must be the case that there are at least two people at the meeting who have the same number of friends.

$\blacksquare$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.