538 Riddler: The Perplexing Puzzle Of The Proud Partygoers

It's party time at this week's Riddler:

It’s Friday and that means it’s party time! A group of people are in attendance at your shindig, some of whom are friends with each other. (Let’s assume friendship is symmetric — if person A is friends with person B, then B is friends with A.) Suppose that everyone has at least one friend at the party, and that a person is “proud” if her number of friends is strictly larger than the average number of friends that her own friends have. (A competitive lot, your guests.)

Importantly, more than one person can be proud. How large can the share of proud people at the party be?

This is the type of puzzle I'd normally try to simulate first to get an idea of what the answer might be.  I think this one seems easy enough to solve directly, though I've thought that before and my initial impressions turned out to be wrong, so we'll see.

It should be easy to see that 100% of the people at the party can't all be proud.  In order for someone to be proud, at least one of their friends must have fewer friends.  For that person to be proud, one of their friends must have fewer friends, and on and on we go until we get to some hypothetical person that has the fewest friends out of everyone.  That last person clearly cannot be proud, because all of their friends have even more friends than they do.

(It also follows from the fact that the sum of all the friendships at the party can't be more than the sum of all the averages, because someone with more friends contributes more frequently to the averages than someone with fewer friends.)

This leads us to the next question: Can N-1 people be proud?  Similar reasoning shows that they cannot.  First, we should note that because everyone at the party must have at least one friend, and no one can have more than N-1 friends, then by the pigeonhole principle at least two people have the same number of friends.  If these two people have the least number of friends at the party, then neither of them is proud.  If they are somewhere further up the chain, then again by the pigeonhole principle we're going to reach a point where we run out of places to assign friends while ensuring that everyone has at least one friend with fewer friends than they do.

For example, imagine that one person has one friend, and two people have two friends.  In order for both of the latter people to be proud, each of them must be friends with the person who has one friend.  But that's obviously a contradiction, and the only way to resolve it is to make the person with one friend have two friends.  But now all three of these people have the fewest friends at the party, and thus none of them are proud.

So N-1 is too many, but it's easy to see how N-2 people can be proud.  Let's call two people at the party Andy and Bill.  Of the rest of the N-2 partygoers, assume they're all friends with each other.  In addition, half of them are friends with Andy (but not Bill) and the other half are friends with Bill (but not Andy).*  Thus, all of these N-2 people have N-2 friends.  And all of their friends have N-2 friends, except for Andy/Bill, who each have (N-2)/2 friends.  So their average works out to:

\displaystyle \frac{(N-3)(N-2) + \frac{N-2}{2}}{N-2} = (N-3) + \frac{1}{2}

\displaystyle = N - 2.5

Since N-2 > N-2.5, all of these N-2 guests are proud.  So the largest possible proportion of proud people at the party is \displaystyle \frac{N-2}{N}.

* - They don't have to be split in half like that, I just chose that so I could easily show the example mathematically.  It's sufficient to say that some of the N-2 guests are friends with Andy, and the rest are friends with Bill.  The point remains that each of the N-2 partygoers is friends with N-2 others, but the average of their friends' friends is something less than N-2 because of the inclusion of Andy or Bill.

 

3 comments

  1. Nice write-up. I am not exactly following your N-1 case reasoning. If the minimum degree vertex is > 1, then I don't see a contradiction. If the two vertices of equal degree are both friends with the same lower-degree vertex, and that lower-degree vertex has degree at least 2, then how do you continue the argument?

    1. Oh yeah, we also know the minimum degree vertex is the non-proud vertex, so we can't necessarily descend to 1.

    2. It's basically still the pigeonhole principle, which can be seen by starting at the bottom and working your way up. Consider a party of 5 people A, B, C, D, and E. Assume that the minimum degree vertex is partygoer E, who has 2 friends (let's say he's friends with C and D). A is not friends with E, and of course A is also not friends with himself. This means A can have at most 3 friends. If he has 2 or fewer, we've contradicted our premise, so he must have 3. In order to be proud, he must be friends with someone who has 2 or fewer friends. But we know he isn't, thus we can't form a valid construction.

      I realize that's not a general proof, I'm traveling for work and haven't had a chance to write up a full proof yet, but that's the gist of it. Basically if you start at the bottom and try to populate the party with friends such that all but one of them are proud, you "run out" of places to assign friends without violating one of the conditions we start with.

Leave a Reply