Minimum sum of the squares

Question

Find the smallest value of the expression $$(x_1-x_2)^2+(x_2-x_3)^2+...+(x_{n-1}-x_n)^2+(x_n-x_1)^2,$$ if $x_1,x_2,...,x_n -$ pairwise different integers

My work so far: I have a hypothesis, that the answer is: $1+1+..+1+(n-1)^2=(n-1)+(n-1)^2=(n-1)n$,

but I do not know how to prove it

Answer 1

Building off of gammatester's counterexample, it looks like a correct conjecture might be to run up the odds and down the evens, e.g.,

$$1,3,5,7,9,10,8,6,4,2$$

Note that no matter how you arrange the numbers, the average difference between (circularly) consecutive numbers is always $0$, so in a sense what you're trying to do is find an arrangement that minimizes the variance. I.e., if you fix a circular arrangement and let $X$ be the random variable for the difference between a randomly chosen pair of consecutive numbers, then $V(X)=E(X^2)-E(X)^2=E(X^2)-0$.

Answer 2

Your hypothesis is wrong, look e.g. at $n=4$. Your formula will give the sum $3\times 4 = 12$. But if you take $x_1\dots x_4 = 1,3,4,2\;$ the sum is $2^2 + 1^2 + 2^2 + 1^2 = 10$

Answer 3

For the integers from $1$ to $n$ you can make two differences $1$ and all other differences $2$ by arranging the numbers as:-

$$..., 5,3,1,2,4,6....$$ with $n$ eventually reached on one side or another.

This gives a total of $4n-6$.

Note that there is no loss of generality in assuming that integers are from $1$ to $n$ because:

they can be translated until the smallest $x_i$ is $1$;

if the largest $x_i$ were greater than $n$ then we could simply reduce $2f$ by subtracting 1 from some of the larger $x_i$ without making two of the $x_i$ equal.

Proof

In general, we have two chains of numbers from $1$ to $n$ and therefore we have $n$ integers (the differences) such that$$d_1+d_2+...+d_n=2(n-1) \;\;\;\;(1)$$ and we wish to prove that $$d_1^2+d_2^2+...+d_n^2\ge 4n-6.$$

We can assume the $d_i$ are non-negative. Suppose two of the $d_i$ were $a$ and $b$ where $b\ge a+2$. Then replacing $a$ and $b$ by $a+1$ and $b-1$ decreases the sum of squares.

Therefore, for the minimum, the $d_i$ can only take two values which differ by $1$. From equation (1) these values must be $1$ and $2$ giving the above solution.