Here is the problem:
There are 2000 people on a social network. Each person sends 1000 friend requests. Two people are friends if they've sent a friend request to each other. What is the minimum possible number of friendships on this social network?
I have one idea, but it seems wrong to me. Maybe result is fine, but reasoning may be wrong.
Total number of edges should be $2\ 000 \times 1\ 000 = 2\ 000\ 000$.
Observe complete graph with $2\ 000$ vertices, but between each two vertices there is only one-directional link because we don't want any friendships. In that graph there are $\frac{2\ 000 \times 1\ 000}{2} = 1\ 999\ 000$ edges. $2\ 000\ 000 - 1\ 999\ 000 = 1\ 000$ edges are missing, so we add them and now for each edge one new friendship is formed. And the answer is $1\ 000$.
But can I guaranty here that there will be exactly $1\ 000$ outgoing edges from each vertex?
Take two people, Alice and Bob from the graph. Have them send friend requests to each other. Now they are friends, and have 999 friend requests remaining.
Next, divide the remaining people into two equal sets, A and B, with each set containing 999 people. Alice sends her 999 remaining friend requests to everyone in A. Bob sends his to everyone in B. Meanwhile, everyone in B sends one request to Alice, and everyone in A sends one request to Bob.
Now Alice and Bob have used up all their requests, and everyone in A and B has 999 requests remaining. This process has resulted in exactly one friendship, and has reduced the size of the problem from 2000 people with 1000 requests each to 1998 people with 999 requests each.
So the minimum number of friendships created is at most 1000.
Can we prove this is optimal?
The number of possible friendships is ${}_{2000}C_2 = \frac{2000\cdot1999}{2} = 1999\cdot1000$. Everyone gets to send 1000 friend requests, but since there are 2000 people, (and 1999 people other than the person in question,) we can view this as saying that everyone get to not send 999 friend requests. For a friendship not to happen, one person of the two must use up one of their non-requests to prevent it. Thus, the number of friendships that can be prevented is the total number of non-requests, or $2000\cdot999 = 1998\cdot1000$. Thus, the number of friendships that absolutely cannot be prevented no matter what is $1999\cdot1000 - 1998\cdot1000 = 1000$.
So the proposed minimum, 1000, is optimal.