Party people
Is it possible to hold a party at which no two people have the same number of friends as each other?
The solution
The answer is no, it is not. The proof is a so-called "proof by contradiction": suppose the opposite and show that this inexorably leads to a contradiction.
So we start by supposing that we have a party, with N people attending, and that no two of those people know the same number of people as each other. Since the most friends anyone can have at the party is N-1, and the fewest is 0, there must be exactly one person with each number of friends between 0 and N-1 inclusive.
But the person with N-1 friends knows everybody at the party - including the person with no friends! This is the contradiction, and it implies that the assumption wasn't true: there cannot be such a party.
Back to main puzzle page