Mathematical Olympiad in Ukraine, Fourth Round (March 24, ), 2010

Answer: $4n - 6$.

We prove by induction that
$$(x_1 - x_2)^2 + (x_2 - x_3)^2 + \dots + (x_{n-1} - x_n)^2 + (x_n - x_1)^2 \geq 4n - 6,$$
if $x_1, x_2, \dots, x_n$ are distinct integer numbers.

The base is trivial. Indeed, $S_2 = (x_1 - x_2)^2 + (x_2 - x_1)^2 \geq 2$, because all numbers are integer and distinct.

Let us now suppose that our assumption holds for $n$, in other words,
$$(x_1 - x_2)^2 + (x_2 - x_3)^2 + \dots + (x_{n-1} - x_n)^2 + (x_n - x_1)^2 \geq 4n - 6.$$
Let $x_1, x_2, \dots, x_n, x_{n+1}$ be distinct integer numbers. WLOG, we can assume that $x_{n+1}$ is a maximum among our numbers. We now have
$$(x_n - x_{n+1})^2 + (x_{n+1} - x_n)^2 - (x_n - x_1)^2 = (x_{n+1} - x_n)(x_{n+1} - x_1) \geq 4.$$
Summing all such inequalities and using our induction hypothesis we get the desired result for $n + 1$ numbers.

We now construct example, that proves sharpness of our bound.
For $n = 2k - 1$ one can take $x_j = 2j - 2$ for $j \leq k$ and $x_j = -2j + 4k - 1$ for $j \geq k + 1$.
For $n = 2k$ we take $x_j = 2j - 2$ for $j \leq k$ and $x_j = -2j + 4k + 1$ for $j \geq k + 1$.

Alternative solution:
Let us assume, that $x_1$ is a maximum and $x_k$ is a minimum among our numbers. Then, we have $x_1 - x_k \geq n - 1$. By AM-GM:
$$\begin{aligned} & \sum_{j=1}^{n} (x_j - x_{j+1})^2 \geq \frac{1}{n} \left( \sum_{j=1}^{n} |x_j - x_{j+1}| \right)^2 \\ & \geq \frac{((x_1 - x_2) + \dots + (x_{k-1} - x_k) + (-x_k + x_{k+1}) + (-x_{k+1} + x_{k+1}) + \dots + (-x_n + x_1))^2}{n} \\ & = \frac{(2(x_1 - x_k))^2}{n} \geq \frac{(2(n-1))^2}{n} = 4n - 8 + \frac{4}{n}. \end{aligned}$$
$\sum_{j=1}^{n} (x_j - x_{j+1})^2$ is natural, thus $\sum_{j=1}^{n} (x_j - x_{j+1})^2 \geq 4n - 7$. Moreover, squaring does not change a parity of an expression and $\sum_{j=1}^{n} (x_j - x_{j+1}) = 0$ is even, then $\sum_{j=1}^{n} (x_j - x_{k+1})^2$ is also even. Hence, it is not less than $4n - 6$.