MathDB

In a country, there are

{}N{}

cities and

N(N-1)

one-way roads: one road from

X{}

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{}

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

Problem Statement