I encountered this problem in Peter Winkler's book "Mathematical Puzzles: A Connoisseur's Collection". I didn't check the solution there, so it might be more elegant than my proof below, but anyway:

No, it is impossible that the idiot pays less than the genius.

In order to see this, we will show that for every travel cost of the idiot, there is a travel cost of the genius, which is equal or cheaper, and all these genius' travels are different.

Let's assume the idiot travelled the towns in order $1 \rightarrow 2\rightarrow ... \rightarrow n$. If the genius visited town $n-1$ before town $n$, then we pair the idiot's travel $(n-1, n)$ with the genius' travel $(n-1, *)$. Notice that $C(n-1,*)<C(n-1,n)$ and everything is fine so far. If the genius visited also town $n-2$ before town $n$, then we pair the idiot's travel $(n-2, n-1)$ with the genius' travel $(n-2,*)$. Notice that $C(n-2,*)<C(n-2,n)<C(n-2,n-1)$, so again everything is fine. We continue like this, until we get to some town $k$ which the genius visited after town $n$. Then we pair the idiot's travel $(k,k+1)$ with the genius' travel $(n,*)$. Notice that $C(n, *)<C(n,k)<C(k,k+1)$, so once again everything is fine. Now we continue by checking whether the genius visited town $k-1$ before  $k$ and pairing the idiot's travel $(k-1,k)$ with either $(k-1,*)$ or with $(k,*)$ from the genius.

We keep going like this, until eventually pair all idiot's travels with genius' travels and solve the problem.

I encountered this problem in Peter Winkler's book "Mathematical Puzzles: A Connoisseur's Collection". I didn't check the solution there, so it might be more elegant than my proof below, but anyway:

No, it is impossible that the idiot pays less than the genius.

In order to see this, we will show that for every travel cost of the idiot, there is a travel cost of the genius, which is equal or cheaper, and all these genius' travels are different.

Let's assume the idiot travelled the towns in order $1 \rightarrow 2\rightarrow ... \rightarrow n$. If the genius visited town $n-1$ before town $n$, then we pair the idiot's travel $(n-1, n)$ with the genius' travel $(n-1, *)$. Notice that $C(n-1,*)\leq C(n-1,n)$ and everything is fine so far. If the genius visited also town $n-2$ before town $n$, then we pair the idiot's travel $(n-2, n-1)$ with the genius' travel $(n-2,*)$. Notice that $C(n-2,*)\leq C(n-2,n)\leq C(n-2,n-1)$, so again everything is fine. We continue like this, until we get to some town $k$ which the genius visited after town $n$. Then we pair the idiot's travel $(k,k+1)$ with the genius' travel $(n,*)$. Notice that $C(n, *)\leq C(n,k)\leq C(k,k+1)$, so once again everything is fine. Now we continue by checking whether the genius visited town $k-1$ before  $k$ and pairing the idiot's travel $(k-1,k)$ with either $(k-1,*)$ or with $(k,*)$ from the genius.

We keep going like this, until eventually pair all idiot's travels with genius' travels and solve the problem.

I encountered this problem in Peter Winkler's book "Mathematical Puzzles: A Connoisseur's Collection". I didn't check the solution there, so it might be more elegant than my proof below, but anyway:

No, it is impossible that the idiot pays less than the genius.

In order to see this, we will show that for every travel cost of the idiot, there is a travel cost of the genius, which is equal or cheaper, and all these genius' travels are different. Let's assume the idiot travelled the towns in order $1 \rightarrow 2\rightarrow ... \rightarrow n$. If the genius visited town $n-1$ before town $n$, then we pair the idiot's travel $(n-1, n)$ with the genius' travel $(n-1, *)$. Notice that $C(n-1,*)<C(n-1,n)$ and everything is fine so far. If the genius visited also town $n-2$ before town $n$, then we pair the idiot's travel $(n-2, n-1)$ with the genius' travel $(n-2,*)$. Notice that $C(n-2,*)<C(n-2,n)<C(n-2,n-1)$, so again everything is fine. We continue like this, until we get to some town $k$ which the genius visited after town $n$. Then we pair the idiot's travel $(k,k+1)$ with the genius' travel $(n,*)$. Notice that $C(n, *)<C(n,k)<C(k,k+1)$, so once again everything is fine. Now we continue by checking whether the genius visited town $k-1$ before $k$ and pairing the idiot's travel $(k-1,k)$ with either $(k-1,*)$ or with $(k,*)$ from the genius. Eventually, we would pair all idiot's travels with genius' travels and will solve the problem.

I encountered this problem in Peter Winkler's book "Mathematical Puzzles: A Connoisseur's Collection". I didn't check the solution there, so it might be more elegant than my proof below, but anyway:

No, it is impossible that the idiot pays less than the genius.

In order to see this, we will show that for every travel cost of the idiot, there is a travel cost of the genius, which is equal or cheaper, and all these genius' travels are different.

Let's assume the idiot travelled the towns in order $1 \rightarrow 2\rightarrow ... \rightarrow n$. If the genius visited town $n-1$ before town $n$, then we pair the idiot's travel $(n-1, n)$ with the genius' travel $(n-1, *)$. Notice that $C(n-1,*)<C(n-1,n)$ and everything is fine so far. If the genius visited also town $n-2$ before town $n$, then we pair the idiot's travel $(n-2, n-1)$ with the genius' travel $(n-2,*)$. Notice that $C(n-2,*)<C(n-2,n)<C(n-2,n-1)$, so again everything is fine. We continue like this, until we get to some town $k$ which the genius visited after town $n$. Then we pair the idiot's travel $(k,k+1)$ with the genius' travel $(n,*)$. Notice that $C(n, *)<C(n,k)<C(k,k+1)$, so once again everything is fine. Now we continue by checking whether the genius visited town $k-1$ before $k$ and pairing the idiot's travel $(k-1,k)$ with either $(k-1,*)$ or with $(k,*)$ from the genius.

We keep going like this, until eventually pair all idiot's travels with genius' travels and solve the problem.