Serbian Mathematical Olympiad

Solution:

The condition of the problem gives us $0 \leqslant (d_{i}-1)(2010-d_{i})$ for all $i$, i.e. $d_{i}^{2} \leqslant 2011 d_{i}-2010$. Using the condition $\sum_{i=1}^{n} d_{i}=2 m$, by summing these inequalities we obtain
$$\sum_{i=1}^{n} d_{i}^{2} \leqslant 2011 \cdot \sum_{i=1}^{n} d_{i}-2010 n=4022 m-2010 n$$
and equality holds if and only if $d_{i} \in\{1,2010\}$ for every $i \in\{1,2, \ldots, n\}$.

$1^{\circ}$ Let $n=2 k, k \in \mathbb{N}$. If we establish an airline route between cities $i$ and $j$ if and only if $|j-i|=k$, we have $d_{i}=1$ for all $i$.

$2^{\circ}$ Let $n=2 k-1, k \in \mathbb{N}$. It cannot be that $d_{i}=1$ for all $i$, because otherwise we would have $2 m=n=2 k-1$. Therefore it must be that $d_{j}=2010$ for some $j$; hence $n \geqslant 2011$. On the other hand, establishing an airline route between cities 1 and $i$ $(1 \leq i \leq 2010)$ and between cities $2 i$ and $2 i+1$ $(i=1006, \ldots, k)$ gives a network in which $d_{1}=2010$ and $d_{i}=1$ for $2 \leqslant i \leqslant n$.

Therefore, equality can be attained if $2 \mid n$, or $2 \nmid n$ and $n \geq 2011$.