Nov 14, 2009

Cocktail Party

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 is a friend of y, then y is a friend of x.)

Hint: Use pigeonhole principle

1 comment:

  1. 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.