2019 CNMO P7
Source: 2019 China North MO, Problem 7
February 22, 2020
combinatorics
Problem Statement
There are 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 th time, set up a two-way air line between city 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.