Prove there exist numbers $a_i, b_j$ so that $x_{ij}=a_i + b_j$ for all $1\le i,j\le n$ if any full tour costs the same 
In a country with $n$ towns the cost of travel from the $i$-th town to the $j$-th town is $x_{ij}$. Suppose the total cost of any route passing through each town exactly once and ending at its starting point doesn't depend on which route is chosen. Prove there exist numbers $a_1,\cdots, a_n, b_1,\cdots, b_n$ so that for all $1\leq i, j \leq n, x_{ij}=a_i + b_j$.

Let $f(a,b)=x_{a1}+x_{1b}-x_{ab}$ where $a,b,1$ are distinct. I think $f(a,b)$ is independent of $a$ and $b$ but I'm not sure how to show this. I know $f(a,b)=f(b,c)$ when $a,b,c,1$ are all distinct, and this can be shown by assuming WLOG that $a<b<c$ and considering the two routes $a,b,1,c,2,\cdots, a-1,a+1,\cdots, b-1,b+1,\cdots, c-1,c+1,\cdots, n,a$ and $a,1,b,c,2\cdots, a-1,a+1\cdots, b-1,b+1,\cdots, c-1,c+1,\cdots, n,a.$ The difference between their costs is $x_{ab}+x_{b1}+x_{1c}-x_{a1}-x_{1b}-x_{bc},$ which must be zero by the problem assumption, and rearranging yields $f(a,b) = f(b,c)$.

But is it true that $f(a,b)=f(b,a)$ for $a,b,1$ distinct (*), and if so how would one show this? I tried a similar approach to above, but I didn't make much progress.

Provided (*) holds, we have for $a,b,c,d,1$ all distinct that $f(a,b)=f(b,c)=f(c,d) = f(d,c), f(a,b)=f(b,a)=f(a,c)=f(c,a), f(a,b)=f(b,c)=f(c,b),$
which proves the desired independence.

Provided $f(a,b)$ is independent of $a$ and $b$, for any $1\lt i < j \leq n$, we have $x_{ij} = x_{i1} + x_{ij} - x_{i1} + x_{1j}-x_{1j} = -f(i,j) + x_{i1} + x_{1j}$. So letting $F$ denote the constant value of $f(i,j)$, we can let $a_i = -F + x_{i1}$ and $b_i = x_{1i}$ for $i>1$ and $a_1 = 0, b_1 = F$.

 A: You have done most of the work.

*

*Your have proved that $f(a,b) = f(b,c)$ for any distinct $a, b, c$ none of which is $1$.

*Assuming $f(a,b)=(b,a)$ for distinct $a,b\ne1$, you can construct the wanted numbers $a_i, b_i$.


The cases when $n=1$ and $n=2$ are trivial.
Suppose $n\ge3$. Let us prove $f(a,b) = f(b,a)$ for distinct $a,b\ne1$.
There are three cases.

*

*$n=3$.
Consider route $3,1,2,3$ and route $2,1,3,2$.
The difference of their costs is $f(2,3)-f(3,2)$. Hence $f(2,3)=f(3,2)$.


*$n=4$.
$$\begin{aligned}
  &\quad\ \ 2f(2,3)\\ 
  &= f(2,3) + f(3,4) \\
  &= (x_{21} + x_{13}-x_{23})+ (x_{31}+x_{14}-x_{34})\\
  &= (x_{12} +x_{21} +x_{13} +x_{31} +x_{14} +x_{41}) - (x_{12}+x_{23} +x_{34} +x_{41})\\
  &= (\text{an expression that is symmetric WRT 2,3,4}) - (\text{cost of a Hamiltonian cycle})
  \end{aligned}$$
By symmetry, $f(a,b)$ is a constant.


*$n\ge5$.
We can find two distinct numbers $c$ and $d$ other than $a, b, 1$ between $1$ and $n$.
$$f(a,b)=f(b,c)=f(c,d)=f(d,a)=f(a,c)=f(c,b)=f(b,a)$$
