St Petersburgh 2008 #2
Source:
July 23, 2011
combinatorics proposedcombinatorics
Problem Statement
In a kingdom, there are roads open between some cities with lanes both ways, in such a way, that you can come from one city to another using those roads. The roads are toll, and the price for taking each road is distinct. A minister made a list of all routes that go through each city exactly once. The king marked the most expensive road in each of the routes and said to close all the roads that he marked at least once. After that, it became impossible to go from city to city , from city to city , and from city to city . Prove that the kings order was followed incorrectly.