The Perplexing Puzzle Of The Proud Partygoers

A group of $N$ people are at a party, some pairs of them friends (friendship is mutual). Everyone has at least one friend present. Call a guest proud if her own number of friends is strictly larger than the average number of friends her friends have. More than one guest can be proud. How large can the share of proud guests be?

The Riddler, FiveThirtyEight (Dominic van der Zypen)(original post)

Solution

Pride is a contrast: you are proud when you are better-connected than the friends you keep. The way to manufacture it wholesale is to make almost everyone the better-connected one, and a single missing friendship does exactly that.

Start from the fully connected party, where everyone is friends with everyone. All $N$ guests have $N-1$ friends, so nobody’s count beats the average around them, and no one is proud. Now remove one friendship, between two guests $X$ and $Y$. Their counts fall to $N-2$; every other guest still has $N-1$.

Look at any of the other $N-2$ guests. She has $N-1$ friends, and that circle includes both $X$ and $Y$ (each at $N-2$) alongside guests at $N-1$. Her friends’ average is therefore a shade below $N-1$, and her own $N-1$ strictly tops it. She is proud. Now look at $X$. His $N-2$ friends are everyone except $Y$, and none of them lost an edge, so each still has $N-1$ friends. Their average is $N-1$, above his $N-2$; he is not proud, and by symmetry neither is $Y$.

So all but two guests are proud, a share of $$\boxed{\dfrac{N-2}{N}},$$ which climbs toward $1$ as the party grows. The two stragglers are unavoidable: in any party the most-connected guest has every friend at a friend-count no larger than her own, so her friends’ average can never fall strictly below her count, and she is never proud. That keeps the share under $1$ always, and an exhaustive check of small parties confirms $N-2$ proud guests is the most any arrangement allows.

The computation

Build the complete graph on $N$ guests, delete one edge, and count the proud. A separate brute force over every graph on a handful of guests confirms that $N-2$ is genuinely the ceiling, not merely what this construction reaches.

from itertools import combinations, product

def proud_count(adj, N):
    deg = {i: len(adj[i]) for i in range(N)}
    return sum(1 for i in range(N)
               if deg[i] > sum(deg[j] for j in adj[i]) / deg[i])

def complete_minus_edge(N):                 # the construction
    adj = {i: set(range(N)) - {i} for i in range(N)}
    adj[0].discard(1); adj[1].discard(0)
    return proud_count(adj, N)

def best_over_all_graphs(N):                # exhaustive optimum
    edges, best = list(combinations(range(N), 2)), 0
    for mask in product((0, 1), repeat=len(edges)):
        adj = {i: set() for i in range(N)}
        for on, (u, v) in zip(mask, edges):
            if on: adj[u].add(v); adj[v].add(u)
        if all(adj[i] for i in range(N)):   # everyone needs a friend
            best = max(best, proud_count(adj, N))
    return best

for N in (4, 5, 6):
    print(N, complete_minus_edge(N), best_over_all_graphs(N), N - 2)
# 4 2 2 2
# 5 3 3 3
# 6 4 4 4      <- construction meets the exhaustive maximum, both equal N-2