http://www.artofproblemsolving.com/Forum/viewtopic.php?t=364267

Start a person at each vertex. Sort the edges from most expensive to least expensive. Over all the edges, swap the people at the two edges every time, in the order from least to most. Observe that each of the people trace out a decreasing path, almost by definition. There are $n$ paths traced out, and the sum of their lengths is $2 \times \dbinom{n}{2} = n(n-1)$, so by the piegonhole principle, at least one path has length $n-1$.

va2010 wrote: There are $n$ paths traced out, and the sum of their lengths is $2 \times \dbinom{n}{2} = n(n-1)$, so by the piegonhole principle, at least one path has length $n-1$. Your solution is right, I will explain specifically: Greedy Algorithm: Starting at vertex $v_1$ and we goes to $v_2$ such that the price of route $v_1\longrightarrow v_2$ is the largest among all the neighbors of $v_1.$ Finally we terminate at $v_k$ for some integer $k.$ Applying this algorithm to each vertex, we obtain $n$ paths. Claim: Let $U,V$ be arbitrary two distinct cities, there exists at least $1$ path which contain $U\longrightarrow V.$ Proof. Just inverse the above greedy algorithm: set $V=A_0,U=A_1,$ we select $A_2$ such that the price of route $A_2\longrightarrow A_1$ is minimum, finally we terminate at $A_t$ and we get a path $A_t\longrightarrow A_{t-1}\longrightarrow\dots\longrightarrow A_1\longrightarrow A_0$ as desired. $\blacksquare$ Hence by PHP one of the $n$ path must have length at least $\frac{2\binom{n}{2}}{n}=(n-1)$, as required.

Complex2Liu wrote: va2010 wrote: Claim: Let $U,V$ be arbitrary two distinct cities, there exists at least $1$ path which contain $U\longrightarrow V.$ Proof. Just inverse the above greedy algorithm: set $V=A_0,U=A_1,$ we select $A_2$ such that the price of route $A_2\longrightarrow A_1$ is minimum, finally we terminate at $A_t$ and we get a path $A_t\longrightarrow A_{t-1}\longrightarrow\dots\longrightarrow A_1\longrightarrow A_0$ as desired. $\blacksquare$ Can you please explain this part I don't understand why this is true for every U and V

Cute. Label the vertices $1, 2, 3, \dots, n$, and denote by $P_i$ the path that starts at $i$ such that at every point, we greedily choose the largest train that still has a smaller fare. Claim. Every train route $a \to b$ and $b \to a$ appears in exactly one of these paths. Proof. ``Greedy induction": we consider one-directional routes. The claim is obviously true for the most expensive route, say $i \to j$; then, to have taken the second most expensive train out of $j$, the traveler must have taken the previous train $i \to j$, which appears in exactly one path; hence this next expensive train $j \to k$ appears only in that path. We may iterate this process without issues until all directed edges are covered. $\blacksquare$ Hence the average length of a path is $\frac{2{n \choose 2}}n = n-1$, and hence one such path must have length at least $n-1$.

$ $

Attachments: