Fall Mathematical Competition

Denote the non-closed airports with $B_1, \dots, B_{999}$ where $B_i = A_i$ for $i = 1, \dots, k-1$ and $B_i = A_{i+1}$ for $i = k+1, \dots, 1000$. Denote the number of the airlines from $B_i$ by $d'_i$. It is clear that $d'_i \ge d_i - 1$ for every $i = 1, \dots, 999$. We can assume without loss of generality that $d'_1 \le d'_2 \le \dots \le d'_{999}$.
Let $X$ be the set of cities which can be reached from $B_{999}$ (after closing $A_k$). It is obvious that $x = |X| \ge d'_{999} + 1 \ge d_{999}$. Let us assume that there exist cities which can not be reached from $B_{999}$ (otherwise we are done). Denote the set of such cities by $Y$ and let $B_u$ be the city of largest index in $Y$. Since $999 - x \le 999 - d_{999}$ we have
$$d'_{u} \ge d'_{999-x} \ge d_{999-x} - 1 \ge (999 - x + 1) - 1 = 999 - x,$$
i.e. $|Y| \ge 1000 - x$. Then we have
$$|X \cap Y| = |X| + |Y| - |X \cup Y| \ge x + (1000 - x) - 999 \ge 1,$$
a contradiction.