medium | discrete |

At a party of $N$ people, there are some friendships. Prove that there are at-least two people with the same count of friends.

Assume that $N \ge 2$ and that the friendships are symmetric, i.e, if $A$ is friends with $B$, then $B$ is in turn friends with $A$.

Pigeonhole Principle

Since there are $N-1$ possibilities for friend-count and total $N$ people, atleast two people must have the same count.

The question can be solved by using the Pigeonhole Principle, which essentially states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with more than one pigeon.

In this party of $N$ people, indexed from $1$ to $N$. The maximum number of friends a person can have is $N-1$, because one can be friends with every other person but not with oneself. So the possible number of friends one can have ranges from $0$ to $N-1$, a total of $N$ possibilities.

Note: If someone has zero friends, then someone else can have atmost $N-2$ friends, alternatively if someone has $N-1$ friends then someone else must have at-least $1$ friends.

Hence, the total possibilities of the count of friends ranges from $0$ to $N-2$ or from $1$ to $N-1$, i.e, total $N-1$ possibilities, but there are only $N$ people at the party.

Let's consider the count of friends as "pigeonholes" and people as "pigeons". Notice that there are $N$ people ("pigeons") and $N - 1$ different count of friends ("pigeonholes").

So, by the Pigeonhole Principle, at least two people must have the same count of friends in the party of $N$ people.

There's another way to solve this.

**Proof by Contradiction**: Assume that every person has a different number of friends from $0$ to $N - 1$. We would have a situation where one person has $0$ friends and another person has $N-1$ friends. This, however, contradicts the premise that friendships are symmetric, because if one person has $N-1$ friends, there cannot be someone with $0$ friends. Hence not everyone has a different number of friends