Team Selection Test for JBMO

The answer is $k=3$.

We will write $A\to B$ if flight is from $A$ to $B$. The flight arrangement where $A\to B\to C\to A$ and all other flights incident to $A,B,C$ are directed to $A,B,C$ shows that $k\le 3$.

If a city $A$ is reachable from any other city by using at most two flights we will say that $A$ is 2-reachable. Now we show that in any flight arrangement there are at least three cities 2-reachable from any city.

The problem can be reformulated in terms of graph theory: Let $G$ be a directed complete graph with $2013$ vertices. If the incoming degree ${\mathrm{deg}}_{\text{in}}(A)$ of each vertex $A$ is at most $n-2$, then there are $3$ vertices 2-reachable from any other vertex.

First of all, let us show that a vertex with maximal incoming degree, say $A_1$, is 2-reachable. Let $U_1$ be the set of all vertices $X$ with $A_1\to X$ and $W_1$ be the set of all vertices $Y$ with $Y\to A_1$. $A_1$ is reachable from any $Y\in W_1$ directly. If $A_1$ is not 2-reachable from some $X_0\in U_1$, then for any $Y\in W_1$ we have $Y\to X_0$; otherwise $A_1$ is 2-reachable from $X_0$: $X_0\to Y\to A_1$. But then ${\mathrm{deg}}_{\text{in}}{X}_0={\mathrm{deg}}_{\text{in}}(A_1)+1$, which contradicts the maximality of ${\mathrm{deg}}_{\text{in}}{A}_1$.

Now let $A_2$ be a vertex in $U_1$ with maximal incoming degree ${\mathrm{deg}}_{\text{in}}{A}_2$ (note that $U_1$ is not empty). Let $U_2$ be the set of all vertices $X$ with $A_2\to X$ and $W_2$ be the set of all vertices $Y$ with $Y\to A_2$. $A_2$ is reachable from any $Y\in W_2$ directly. If $A_2$ is not 2-reachable from some $X_0\in U_2$, then for any $Y\in W_2$ we have $Y\to X_0$; otherwise $A_2$ is 2-reachable from $X_0$: $X_0\to Y\to A_2$. But then ${\mathrm{deg}}_{\text{in}}{X}_0={\mathrm{deg}}_{\text{in}}(A_2)+1$, which contradicts the maximality of ${\mathrm{deg}}_{\text{in}}{A}_2$.

Now let $A_3$ be a vertex in $U_2$ with maximal incoming degree ${\mathrm{deg}}_{\text{in}}{A}_3$ (note that $U_2$ is not empty). Let $U_3$ be the set of all vertices $X$ with $A_3\to X$ and $W_3$ be the set of all vertices $Y$ with $Y\to A_3$. $A_3$ is reachable from any $Y\in W_3$ directly. If $A_3$ is not 2-reachable from some $X_0\in U_3$, then for any $Y\in W_3$ we have $Y\to X_0$; otherwise $A_3$ is 2-reachable from $X_0$: $X_0\to Y\to A_3$. But then ${\mathrm{deg}}_{\text{in}}{X}_0={\mathrm{deg}}_{\text{in}}(A_3)+1$, which contradicts the maximality of ${\mathrm{deg}}_{\text{in}}{A}_3$.

Thus, we have found three vertices 2-reachable from any other city. $A_1,A_2,A_3$ are distinct and the proof is completed (if we proceed the same way, the new found point $A_4$ may coincide with $A_1$).