Problem 1147

86.42. Suppose that the airline $A B$ is closed, and assume that the shortest route from city $X$ to city $Y$ now has a length of $2 n+1$ stops. Let's number the cities in this flight from $X_{0}=X$ to $X_{2 n+1}=Y$. Previously, there was the shortest flight from $X$ to $X_{i+1}$, requiring no more than $n$ stops, and a flight from $X_{n}$ to $Y$, also requiring no more than $n$ stops. Clearly, both flights passed through the line $A B$, and we can assume that the flight along it was in the direction from $A$ to $B$. Let the number of stops in the flight $X-X_{n+1}$ from $X$ to $A$ be $s_{1}$, and from $B$ to $X_{n+1}$ be $t_{1}$; in the flight $X_{n}-X_{2 n+1}$ from $B$ to $X_{2 n+1}$ be $s_{2}$, and from $X_{n}$ to $A$ be $t_{2}$.

Then, by the condition, $s_{1}+1+t_{1} \leqslant n, s_{2}+1+t_{2} \leqslant n$. Adding these inequalities, we get $\left(s_{1}+t_{2}\right)+\left(s_{2}+t_{1}\right) \leqslant 2 n-2$, and therefore one of the terms on the left side does not exceed $n-1$. But this means that there is a flight from $X$ to $X_{n}$ or from $X_{n+1}$ to $X_{2 n+1}$ of length less than $n$ and not including the line $A B$ - a contradiction.