Iranian Mathematical Olympiad

We claim that independent of the way we shall choose $n$ persons, the parity of the number of friendship relations among them is equal to the parity of $n - a$. We shall prove the following lemma;

Lemma 1. If we replace one person with her antipodal the parity of number of friendship relations among the people would not change.

Proof. Let us assume that the chosen person has two friends, namely $A$ and $B$. Assume the antipodal person has two friends namely $C$ and $D$. Such that $A, C$ as well as $B, D$ are antipodal. Since $n \le a$ we can find that these four persons are indeed distinct. Thus, if the number of chosen persons from the set $\{A, C\}$ is $i$ the number of chosen persons from the set $\{B, D\}$ would be $2 - i$. Hence, after the replacements the total number of friendship relations between the chosen persons would change by $i - 2 - i = 2$. Hence, the parity remains unchanged. This completes our proof.

According to the above lemma, after the replacing any one with the person who is her antipodal, we can assume that the chosen persons have the numbers $\{1, 2, \dots, n\}$. Thus, in between there are $2a$ persons who have 1 friend and $n - 2a$ who have 2 friends. Thus, the total number of friendship relations is $n - a$. Thus, the answer would be all $(n, a)$ such that $n \equiv 1 + a \pmod 2$. $\blacksquare$