## Party people solution

Submitted by plusadmin on March 1, 2005## 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