Let $G(V,E)$ be a graph with the set of vertices $V=\{1,2,\ldots,n\}$ and the set of edges $E$, $|E|=m$, that represents the towns and air transportations among them. Two towns are connected iff there is an airline connecting them. The degree of the vertex $i$ is thus $d_i$, where $1 \leq d_i \leq K$ for some integer $K$. Thus, \[\sum_{i=1}^n \left(K-d_i\right)\left(d_i-1\right) \geq 0\] and \[\sum_{i=1}^n \left(K-d_i\right) = Kn - 2m\,.\] Add the two results to get \[\sum_{i=1}^n \left(K-d_i\right)d_i \geq Kn-2m\,.\] Therefore, \[\sum_{i=1}^n d_i^2 \leq \sum_{i=1}^n Kd_i -(Kn-2m) = 2(K+1)m-Kn\,.\] The equality holds iff $d_i \in \{1,K\}$ for all $i$. Assume that $G$ must be a simple graph. If $d_i=1$ for all $i$, then $n$ can be an arbitrary positive even integer. If $d_i=K$ for some $i$, then $n \geq K+1$ is a must. It is easy to construct $G(V,E)$ with $K+1+2\ell$ vertices ($\ell$ is a nonnegative integer). Consequently, for even $K$, all possible $n$ are 1) all positive even integers less than or equal to $K$, and 2) all integers larger than $K$. For odd $K$, then $n$ must be even, only! PS: A lower bound is \[\sum_{i=1}^n d_i^2 \geq 2(K+1)m - \left\lfloor\left(\frac{K+1}{2}\right)^2\right\rfloor n\,.\] For each $K$, can you say something about all possible $n$ such that the above inequality becomes an equality?

By conditions we have that $0\le (d_{i}-1)(2010-d_{i})$ holds for each $i$, $d^2_{i}\le 2011d_{i}-2010$. Since $\displaystyle\sum_{i=1}^n d_{i} =2m$, adding these inequalities we get: $\displaystyle\sum_{i=1}^n d^2_{i}\le 2011\cdot \sum_{1}^n d_{i} - 2010n = 4022m-2010n$,as desired. The equality holds if and only if $d_{i}\in \{1,2010\}$ for each $i\in \{1,2,...,n\}$. $1^\circ$ Let $n=2k$ for some $k\in N$.Setting an airline between towns $i$ and $i+k$ for $i=1,...,k$ and no other airlines yields a configuration with $d_{i}=1$ for all $i$. $2^\circ$ Let $n=2k-1$ for some $k\in N$. We cannot have $d_{i}=1$ for all $i$ because the sum of all $d_{i}$ must be even, so we must have $d_{j}=2010$ for some $j$;hence $n\geq 2011$. On the other hand, setting an airline between towns $2i$ and $2i+1$ for $i=1006,...,k$ and between $1$ and $i$ for $1\le i\le 2010$ yields a configuration with $d_{1}=2010$ and $d_{i}=1$ for $i=2,...,n$. Therefore the equality can be attained if and only if $2|n$, or $2\not|n$ and $n\geq 2011$.

Multiply both sides by 4 and now we have to prove that : $ (4d_{1}^2-8044d_{1})+ . . . +(4d_{n}^2-8044d_{n})<=-8040n $.When we rewrite this we get that we need to prove: $ (2d_1-2011)^2+ . . . +(2d_n-2011)^2 <=2011^2n -8040n=2009^2n $.Now since $ d_i<=2010$ we have that: $ (2d_1-2011)^2+. . .+(2d_n-2011)^2 <=2009^2n $.Obviously equation then holds if $d_i=2010$ so it can be achieved for every $ n>=2011 $.It can easily be proven that for any n greater than 2010 it is possible to make airlines such that every town has exactly 2010.

oh my god in the problems description says for i=1,.....,2010 but all of you guys solved it for i=1,....,n. you know its a huge difference ....

Is this a problem for $i = 1,2, ... 2010$ or for $i = 1,2, ..., n$? If it is for n, it is a very easy problem.