RU-ALLRUSSIAN 2023 Problem 118

In a country, there are ${}N{}$ cities and $N(N-1)$ one-way roads: one road from $X{}$ to $Y{}$ for each ordered pair of cities $X \neq Y$ . Every road has a maintenance cost. For each $k = 1,\ldots, N$ let's consider all the ways to select $k{}$ cities and $N - k{}$ roads so that from each city it is possible to get to some selected city, using only selected roads.

We call such a system of cities and roads with the lowest total maintenance cost $k{}$ -optimal. Prove that cities can be numbered from $1{}$ to $N{}$ so that for each $k = 1,\ldots, N$ there is a $k{}$ -optimal system of roads with the selected cities numbered $1,\ldots, k$ .

Proposed by V. Buslov