Problem

Source: Baltic Way 2010

Tags: combinatorics proposed, combinatorics



There are some cities in a country; one of them is the capital. For any two cities A and B there is a direct flight from A to B and a direct flight from B to A, both having the same price. Suppose that all round trips with exactly one landing in every city have the same total cost. Prove that all round trips that miss the capital and with exactly one landing in every remaining city cost the same.