# Can the stupid salesman do better?

Consider $n$ points $x_1,\ldots,x_n$ on the unit circle $S^1\subset \mathbb{C}$. Suppose these are ordered such that $\sum_{i=1}^n |x_i-x_{i+1}|$ (indices modulo $n$) is maximal for all possible permutation of indices, i.e. going from $x_1$ to $x_2$ to $x_3$ ... to $x_n$ to $x_1$ on straight lines in the complex plane describes the longest possible path to visit each $x_i$ exactly once. Let $c_i:=|x_i-x_{i+1}|$ for $i=1\ldots n$ and $\sigma$ a permutation such that $$c_{\sigma(1)}\geq c_{\sigma(2)}\geq \ldots \geq c_{\sigma(n)}.$$

For an arbitrary point $z\in S^1$ define $d_i:=d_{z,i}:=|z-x_i|$ and let $\tau:=\tau_z$ be a permutation such that $$d_{\tau(1)}\geq d_{\tau(2)}\geq \ldots \geq d_{\tau(n)}.$$

The question is: Is there a choice for $z$ such that for all $i=1\ldots n$ the inequalities $d_{\tau(i)}\leq c_{\sigma(i)}$ hold?

Sometimes yes and sometimes no. If the $x_i$ are an odd number of equally spaced points then all the $c_i$ are equal and less than $d_{ \tau(1)}$ (whatever $z$ is.) However if the $x_i$ are an even number of points tightly clustered half each at the top and bottom then all the $c_i$ will be nearly $2$ (the diameter) but a $z$ near the middle will have all the $d$ about $\sqrt{2}.$
• Right, that's the basic kind of example one might think of. I don't get your first point, though. If the $x_i$ are equally spaced, then for $z=x_j$ we have $d_{\tau(1)}=|x_j-x_k|$ for some $k$ and hence $d_{\tau(1)}\leq c_i$ for all $i$. ($z=x_j$ should be allowed.) – Abel Stolz Dec 22 '12 at 11:12