In a certain country, there are $n$ cities. Between every pair of cities, there is a fixed travel cost to go from one city to the other.
An idiot and a genius both decide to tour this country by visiting every city once. They start their tours at the same city. When choosing which city to visit next, the idiot always picks the city that is most expensive to travel to, of the ones not yet visited. Conversely, the genius always chooses the city that is cheapest to travel to. They do not revisit their starting city.
For some really special value of $n$ and travel costs, is it possible for the idiot to spend strictly less than the genius? If not, I demand proof.
Clarification: Travelling from City X to City Y costs the same as travelling from City Y to City X.
(This was a problem I encountered at my math summer camp. I don't know the solution.)
(I'm assuming that the solution has some form of math so I'm tagging with mathematics. Please change if this isn't very right.)