Reply to comment

Party people solution

March 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


  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options

To prevent automated spam submissions leave this field empty.
By submitting this form, you accept the Mollom privacy policy.