There are $5^n$ people at a party. A girl (who is not part of the party) asks each person how many other people they are not friends with. When she sums everyone’s answers, she gets a number that is at most $5^k$, where $n ≤ k < 2n, n, k ∈ N.$ Assuming that each friendship is mutual (Person A is friends with person B, and vice versa) prove that there exists a person who has at least $5^n − 5^{k−n}$ friends.
I think we need to use the pigeonhole principle here, with $5^k$ as the number of holes, but I'm struggling to see what follows.
EDIT: people cannot be friends with themselves
Suppose every person has $<5^n - 5^{k-n}$ friends. Then the girl only hears numbers that are $> 5^{k-n}$. What can you then say about the sum of those numbers?