How Many Friends Are On The Riddler Social Network?

Riddler Express

On a network of $101$ people, every pair is independently friends with probability $\tfrac12$, and friendship is mutual. Pick a random person, Marcia. On average, how many friends does each of Marcia’s friends have?

Solution

Marcia herself has, on average, $\tfrac{100}{2} = 50$ friends, one possible link to each of the other $100$ people. But a friend of Marcia is special: we already know that person is connected to Marcia, so that one edge is guaranteed rather than a coin flip.

Take any friend $F$ of Marcia. Among the other $99$ people (everyone except Marcia and $F$), each is independently a friend of $F$ with probability $\tfrac12$, contributing $\tfrac{99}{2} = 49.5$ friends on average. Adding the guaranteed edge to Marcia, $$\mathbb{E}[\deg F] = 1 + \frac{99}{2} = \boxed{50.5}.$$ This is the friendship paradox in miniature: your friends have more friends than you do, because being someone’s friend is evidence of being well connected.

The computation

Build the random graph, pick Marcia, pick one of her friends at random, and record that friend’s degree, averaged over many graphs.

import numpy as np
rng = np.random.default_rng(0)
def avg_friend_degree(n=101, runs=50_000):
    total = 0; count = 0
    for _ in range(runs):
        A = rng.random((n, n)) < 0.5
        A = np.triu(A, 1); A = A | A.T            # symmetric, no self-loops
        m = rng.integers(n)
        friends = np.flatnonzero(A[m])
        if friends.size:
            f = rng.choice(friends)
            total += A[f].sum(); count += 1
    return total / count
print(avg_friend_degree())                        # ~50.5

Riddler Classic

The sum of the factors of $36$, including $36$ itself, is $91$; and $36$ inches rounds to $91$ centimeters. Find other whole numbers $n$ for which the sum of the factors of $n$ equals $n$ inches converted to the nearest centimeter. How many are there?

Solution

One inch is exactly $2.54$ centimeters, so the puzzle asks for whole numbers $n$ with $$\sigma(n) = \operatorname{round}(2.54\,n),$$ where $\sigma(n)$ is the sum of all divisors of $n$. Dividing, this means the abundancy $\sigma(n)/n$ must sit very near $2.54$: for $n = 36$ it is $\tfrac{91}{36} \approx 2.528$, close enough that $2.54 \times 36 = 91.44$ rounds to exactly $91$. There is no formula for such $n$; we simply scan. Up to a million there are only three: $$\boxed{36,\ 378,\ 49600.}$$ A check on the largest: $2.54 \times 49600 = 125984$, and $49600 = 2^6 \cdot 5^2 \cdot 31$ has $\sigma = (2^7-1)(1+5+25)(1+31) = 127 \cdot 31 \cdot 32 = 125984$.

The computation

Scan each $n$, compute the divisor sum directly, and keep those where it equals the rounded centimeter value.

def sigma(n):
    s, i = 0, 1
    while i * i <= n:
        if n % i == 0:
            s += i + (n // i if i != n // i else 0)
        i += 1
    return s
hits = [n for n in range(2, 1_000_001) if round(2.54 * n) == sigma(n)]
print(hits)                                       # [36, 378, 49600]