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

Question

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$.

Answer 1

You have done most of the work.

1. Your have proved that $f(a,b) = f(b,c)$ for any distinct $a, b, c$ none of which is $1$.
2. 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)$$