ASU 240 All Soviet Union MO 1977 2 tourists to all cities, cheapest ticket
Source:
July 6, 2019
combinatorics
Problem Statement
There are direct routes from every city of a certain country to every other city. The prices are known in advance. Two tourists (they do not necessary start from one city) have decided to visit all the cities, using only direct travel lines. The first always chooses the cheapest ticket to the city, he has never been before (if there are several -- he chooses arbitrary destination among the cheapests). The second -- the most expensive (they do not return to the first city). Prove that the first will spend not more money for the tickets, than the second.