The Party Problem

Problem: At any party of 1000 people, must there always exist two people at the party who have the same number of friends at the party? For the sake of this problem, one cannot be friends with oneself, and friendship is bidirectional.

Solution: This must always happen. Suppose to the contrary, that every person at the party has a different number of friends at the party. The minimum number of friends one could have is 0, while 999 is the maximum. Thus, we have 1000 different numbers to pick from, and 1000 people to assign numbers, where no two people have the same number. So somebody at the party, say Bill, has no friends at the party, while another, say Julie, is friends with everybody. But this means Julie is friends with Bill, which is a contradiction, because Bill has no friends.

The same method obviously works for any party of size n \geq 2.

Advertisements

3 thoughts on “The Party Problem

  1. Pingback: P vs. NP, A Primer (And a Proof Written in Racket) | Math ∩ Programming

    • The proof still holds. And if nobody knows each other, then everybody has zero friends, so there are two people who have zero friends. The point is that we only count friends who are at the party.

      The only way it can be arbitrary is if the concept of friendship is directed.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s