Prove that in any cocktail party with two or more people, there must be at least two people who have the same number of friends. (Assume that "friend" is symmetric-if x is a friend of y, then y is a friend of x.)

The total number of possible friends can be 0,1,2,3, ... n-1 . But we see that if one of them has 0 friends then none of them can have n-1 friends and vice versa. So only one of them can exist. So we have n-1 choices and n people. So by pigeon hole principle two of them must have same number of friends.

The total number of possible friends can be 0,1,2,3, ... n-1 . But we see that if one of them has 0 friends then none of them can have n-1 friends and vice versa. So only one of them can exist. So we have n-1 choices and n people. So by pigeon hole principle two of them must have same number of friends.

ReplyDelete