Team Selection Test for IMO 2009

Suppose that $a$ and $b$ are not friends. If $x$ is a friend of $a$, then by assumption, $x$ and $b$ have exactly one common friend $y$. The function that takes each $x$ to the corresponding $y$ is a bijection between the friends of $x$ and the friends of $y$. Therefore, any two persons who are not friends have the same number of friends.

Let $k$ be a positive integer. Consider the set of persons with exactly $k$ friends and its complement. Since any person in one of these sets must be friends with any person in the other set, at least one of these sets has less than $2$ persons in it. It follows that either there is a person who is friends with everyone or everyone has the same number of friends.

Suppose that everyone has exactly $k$ friends. On the one hand there are $\left(\genfrac{}{}{0ex}{}{2009}{2}\right)$ pairs of persons in this group. On the other hand, since every pair has exactly one common friend, counting the number of pairs of friends of all persons must give the same answer. That is, $2009\left(\genfrac{}{}{0ex}{}{k}{2}\right)=\left(\genfrac{}{}{0ex}{}{2009}{2}\right)$. But this gives $k(k-1)=2008$, which has no solution.

Hence, the only possibility is that $a_1$ is friends with everyone, and $a_{2i}$ and $a_{2i+1}$ are friends for $1\le i\le 1004$. The answer is $2006$.