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^{\prime }$. It is clear that $d_i^{\prime }\ge d_i-1$ for every $i=1,\dots ,999$. We can assume without loss of generality that $d_1^{\prime }\le d_2^{\prime }\le \cdots \le d_{999}^{\prime }$. 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}^{\prime }+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^{\prime }\ge d_{999-x}^{\prime }\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.