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 $\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 $\deg_{\text{in}} X_0 = \deg_{\text{in}}(A_1) + 1$, which contradicts the maximality of $\deg_{\text{in}} A_1$.

Now let $A_2$ be a vertex in $U_1$ with maximal incoming degree $\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 $\deg_{\text{in}} X_0 = \deg_{\text{in}}(A_2) + 1$, which contradicts the maximality of $\deg_{\text{in}} A_2$.

Now let $A_3$ be a vertex in $U_2$ with maximal incoming degree $\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 $\deg_{\text{in}} X_0 = \deg_{\text{in}}(A_3) + 1$, which contradicts the maximality of $\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$).