There are 19,998 people on a social media platform, where any pair of them may or may not be friends. For any group of 9,999 people, there are at least 9,999 pairs of them that are friends. What is the least number of friendships, that is, the least number of pairs of people that are friends, that must be among the 19,998 people?
It is $5 \cdot 9999=49995$. One possible construction is as follows: have the 19,998 people form 3,333 groups of 6 people, and within each group every pair of people are friends. Now, for any group of 9,999 people, say that there are $x_{1}, x_{2}, \ldots, x_{3333}$ people in each of the 6 groups, respectively. Then there are

$$
\frac{1}{2} \sum_{i=1}^{3333} x_{i}\left(x_{i}-1\right)
$$

pairs of friendships total. But we have that

$$
x_{i}\left(x_{i}-1\right) \geq 5 x_{i}-9,
$$

so

$$
\frac{1}{2} \sum_{i=1}^{3333} x_{i}\left(x_{i}-1\right) \geq \frac{1}{2} \sum_{i=1}^{3333}\left(5 x_{i}-9\right)=\frac{1}{2}(9999 \cdot 5-9 \cdot 3333)=9999
$$

as desired.

It remains to show that 49995 pairs of friends is optimal. For what follows, let $9999=N$, so that $19,998=2 N$, and assume that the condition is satisfied. Let the number of pairs of friends be $e$. Designate half of the people as red and the other half as blue, so that the number of pairs of friends who are both red is minimized.

Note that this means that for every pair of people, one red and one blue, we have that the number of red friends of the blue person is at least as many as the number of red friends of the red person, and the inequality is strict if the two people are friends. This is because we can otherwise swap the two people. Now, if every blue person is friends with at least 3 red people, then the total number of friendships, $e$, is at least $N+3 N+N=5 N$ ( $N$ each from the red people and blue people and $3 N$ from the pairs), as desired. If some blue person is friends with at most 2 red people, then every red person is friends with at most 2 red people, so the number of pairs of red friends is at most $N$, with equality only if every red person is friends with exactly 2 red people. But then consider a blue person with 2 red friends; then, they must have a red friend with exactly 2 red friends too, a contradiction.