50th 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+\cdots +(x_{n-1}-x_n{)}^2+(x_n-x_1{)}^2\ge 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\ge 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+\cdots +(x_{n-1}-x_n{)}^2+(x_n-x_1{)}^2\ge 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)\ge 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\le k$ and $x_j=-2j+4k-1$ for $j\ge k+1$. For $n=2k$ we take $x_j=2j-2$ for $j\le k$ and $x_j=-2j+4k+1$ for $j\ge 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\ge n-1$. By AM-GM: $$\begin{array}{rl}& \sum _{j=1}^n(x_j-x_{j+1}{)}^2\ge \frac{1}{n}{\left(\sum _{j=1}^n|x_j-x_{j+1}|\right)}^2\\ & \ge \frac{((x_1-x_2)+\cdots +(x_{k-1}-x_k)+(-x_k+x_{k+1})+(-x_{k+1}+x_{k+1})+\cdots +(-x_n+x_1){)}^2}{n}\\ & =\frac{(2(x_1-x_k){)}^2}{n}\ge \frac{(2(n-1){)}^2}{n}=4n-8+\frac{4}{n}.\end{array}$$ ${\sum }_{j=1}^n(x_j-x_{j+1}{)}^2$ is natural, thus ${\sum }_{j=1}^n(x_j-x_{j+1}{)}^2\ge 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$.