Problem

Source: 2019 China North MO, Problem 7

Tags: combinatorics



There are $n$ cities in Qingqiu Country. The distance between any two cities are different. The king of the country plans to number the cities and set up two-way air lines in such ways: The first time, set up a two-way air line between city 1 and the city nearest to it. The second time, set up a two-way air line between city 2 and the city second nearest to it. ... The $n-1$th time, set up a two-way air line between city $n-1$ and the city farthest to it. Prove: The king can number the cities in a proper way so that he can go to any other city from any city by plane.