Another great problem from the Riddler blog.
A group of N 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?
The solution:
[Show Solution]
The answer is that at most $N-2$ attendees can be proud. To achieve a maximal share of proud people, start with a party where everybody is friends with everybody else and then break one of the friendships. Then, the $N-2$ attendees with intact friendships will be proud and the two attendees with a broken friendship will be non-proud. To show that $N-2$ is really the best we can do, we need to prove that any party must contain at least two attendees that are not proud.
Fact: If an attendee is proud, at least one of her friends must have strictly fewer friends than her. This follows from the definition that an attendee is proud if her number of friends is strictly larger than the average number of friends that her own friends have.
An immediate consequence of the Fact above: in any party, the attendee with the smallest number of friends is always non-proud. And if several attendees share that same minimal number of friends, they are all non-proud. So it’s impossible to have a party where all attendees are proud.
Let’s try to construct a party where $N-1$ attendees are proud. Based on the arguments above, the party must contain a single attendee $A$ that has the minimal number of friends $k$. This will be the non-proud attendee, and all other attendees must be proud. Let $\{B_1,\dots,B_m\}$ be the set of attendees with the second-smallest number of friends, $s > k$.
- Since each $B_i$ is proud, they must be friends with $A$. This follows from the Fact above, because the only attendee with fewer friends than $B_i$ is $A$. Therefore, $A$ is friends with every $B_i$. This means $k \ge m$.
- Since $s > k$ and $k \ge m$, it follows that $m-1 \le s-2$.
Let’s take a closer look at the $s$ friends of $B_i$.
- One of $B_i$'s friends is $A$, who has $k$ friends. Since $s > k$, then $A$ has at least $s-1$ friends.
- At most $m-1$ of $B_i$'s friends can be other $B_j$'s, each of which have $s$ friends. However, since $m-1 \le s-2$, this can account for at most $s-2$ of the friends.
- At least one more friend is required to make the total of $s$, and this friend is neither $A$ nor a $B_j$. So these remaining friends will each have at least $s+1$ friends.
So the average number of friends of all of $B_i$'s friends is at least:
\[
\frac{1}{s}\bigl( (s-1) + (s-2)s + (s+1) \bigr) = s
\]
If the average number of friends is at least $s$, it cannot be strictly less than $s$, which implies that $B_i$ cannot be proud. In summary, the two least popular attendees at any party must be non-proud. This completes the proof that $N-2$ is the largest share of proud partygoers possible.