medium | discrete |
At a party of people, there are some friendships. Prove that there are at-least two people with the same count of friends.
Assume that and that the friendships are symmetric, i.e, if is friends with , then is in turn friends with .
Pigeonhole Principle
Since there are possibilities for friend-count and total 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 people, indexed from to . The maximum number of friends a person can have is , because one can be friends with every other person but not with oneself. So the possible number of friends one can have ranges from to , a total of possibilities.
Note: If someone has zero friends, then someone else can have atmost friends, alternatively if someone has friends then someone else must have at-least friends.
Hence, the total possibilities of the count of friends ranges from to or from to , i.e, total possibilities, but there are only people at the party.
Let's consider the count of friends as "pigeonholes" and people as "pigeons". Notice that there are people ("pigeons") and 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 people.
There's another way to solve this.
Proof by Contradiction: Assume that every person has a different number of friends from to . We would have a situation where one person has friends and another person has friends. This, however, contradicts the premise that friendships are symmetric, because if one person has friends, there cannot be someone with friends. Hence not everyone has a different number of friends