
Solution. Denote by $X_{1}, X_{2}, \ldots X_{n}$ the cities in the country and let $X_{i}$ be connected to exactly $m_{i}$ other cities by direct two-way airline. Then $X_{i}$ is a final destination of $m_{i}$ direct routes and an intermediate stop of $m_{i}\left(m_{i}-1\right)$ non-direct routes. Thus $r=m_{1}^{2}+\ldots+m_{n}^{2}$. As each $m_{i}$ is at most $n-1$ and $13 \cdot 12^{2}<2014$, we deduce $n \geq 14$.

Consider $n=14$. As each route appears in two opposite directions, $r$ is even, so $r \geq 2016$. We can achieve $r=2016$ by arranging the 14 cities uniformly on a circle connect (by direct two-way airlines) all of them, except the diametrically opposite pairs. This way, there are exactly $14 \cdot 12^{2}=2016$ routes.


## C2

In a country with $n$ cities, all direct airlines are two-way. There are $r>2014$ routes between pairs of different cities that include no more than one intermediate stop (the direction of each route matters). Find the least possible $n$ and the least possible $r$ for that value of $n$.
