Question 50
In a country there are $n$ cities, with a two-way express train connecting every pair. The fare is the same in both directions on each train, and different trains have different fares. Prove that a traveler can choose a starting city and take $n-1$ consecutive trains, paying less for each successive train than for the previous one. The traveler may visit a city more than once.