Traveling Salesmen
Between every pair of major cities in Russia, there is a fixed travel cost for going from either city to the other. Traveling salesman Alexei Frugal starts in Moscow and visits all cities exactly once, choosing every time the cheaper flight to a city he has not visited so far. Salesman Boris Lavish starts in St Petersburg and visits all cities exactly once, choosing every time the most expensive flight to a city he has not visited so far. Can Alexei end up spending more money than Boris after they end their journeys?
No, it is impossible. For every trip of Alexei we will choose a trip of Boris, which costs at least as much.
Let the number of cities is n and Alexei visits them in order 1 -> 2 -> … -> n.
If Boris visits city n-1 before city n, then pair Alexei’s trip (n-1, n) with Boris’ trip (n-1, #). Notice that C(n-1, n) < C(n-1, #).
If Boris also visits city n-2 before city n, then pair Alexei’s trip (n-2, n-1) with Boris’ trip (n-2, #). Notice that C(n-2, n-1) < C(n-2, n) < C(n-2, #).
Continue like this until get to a city k which Boris visits after city n. Then pair Alexei’s trip (k, k+1) with Boris’ trip (n, #). Notice that C(k, k+1) < C(k, n) < C(n, #).
Next, check whether Boris visits city k – 1 before city k, and pair Alexei’s trip (k-1, k) with either (k-1, #) or (k, #). Continue like this, until pair all of Alexei trips with more expensive Boris trips.
We do not know where this puzzle originated from. If you have any information, please let us know via email.