Optimizing an expression of sum of squares of difference of arbitrary real numbers and integers

67 Views Asked by At

Given integer $n\ge2$, find the minimum value of $\alpha$ with the following property: for any $n$ real numbers $x_1,\dots,x_n$, there exist integers $k_1,\dots,k_n$ such that $F(k_1,\dots,k_n)≤\alpha$, where$$F=\sum_{1≤i<j≤n}\left(\left(x_i-k_i\right)-\left(x_j-k_j\right)\right)^2$$

My attempt:

For $n=2$:

Denote $x_i-k_i$ by $a, b$. Wlog assume $a≤b$. Then $F=(a-b)^2$.

Since $k_i$ are integers, we can shift $a$ or $b$ by an integer.

If $b>a+1$, then after replacing $a$ with $a+1$, $F$ decreases. So we assume $b≤a+1$, then $|a-b|+|(a+1)-b|=1$, so either $|a-b|$ or $|(a+1)-b|$ is less than $\frac12$, so the minimum of $\alpha$ is $\frac14$, equality obtained when $x_1=0,x_2=\frac12$.


For $n=3$:

Denote $x_i-k_i$ by $a, b, c$. Wlog assume $a≤b≤c$.

Since $k_i$ are integers, we can shift $a,b,$ or $c$ by an integer.

If $b+c>2\left(a+\frac12\right)$, then after replacing $a$ with $a+1$, $(a-b)^2+(a-c)^2=2a^2-2(b+c)a+b^2+c^2$ decreases. Therefore $F$ decreases. So we assume $b+c\le2\left(a+\frac12\right)$.

In the same way, if $a+b<2\left(c-\frac12\right)$, then replacing $c$ with $c-1$ decreases $F$. So we assume $a+b\ge2\left(c-\frac12\right)$.

I happened to find an identity enter image description here $$(a-b)^2+(a-c)^2+(b-c)^2-\frac23 \\=(2a-b-c+1) \left(\frac{4}{3} (a-b)+\frac23 (b-c)\right)\\-\left(\frac{2}{3} (-a-b+2c-1)+2 (b-c)\right) (-a-b+2c-1)$$ Each term is $\le0$, so the minimum of $\alpha$ is $\frac23$, equality obtained when $a=0, b=\frac13, c=\frac23$.


For $n=4$:

Denote $x_i-k_i$ by $a, b, c, d$. Wlog assume $a≤b≤c≤d$.

Since $k_i$ are integers, we can shift $a,b,c,$ or $d$ by an integer.

If $b+c+d>3\left(a+\frac12\right)$, then after replacing $a$ with $a+1$, $(a-b)^2+(a-c)^2+(a-d)^2=3a^2-2(b+c+d)a+b ^2+c^2+d^2$ decreases. Therefore $F$ decreases. So we assume $b+c+d\le3\left(a+\frac12\right)$.

In the same way, if $a+b+c<3\left(d-\frac12\right)$, then replacing $d$ with $d-1$ decreases $F$. So we assume $a+b+c\ge3\left(d-\frac12\right)$.

If $c+d-a-b>1$, replace $a, b$ with $a+1, b+1$ and then $(a-c)^2+ (b-d)^2=\frac12((a+b-c-d)^2+(a-b-c+d)^2)$ decreases, similarly $(a-d)^2+(b-c)^2$ also decreases. Therefore $F$ decreases. So we assume $c+d-a-b\le1$.

I happened to find an identity enter image description here $$(a-b)^2+(a-c)^2+(a-d)^2+(b-c)^2+(b-d)^2+(c-d)^2-\frac{5}{4}=\frac{1}{39}\left(3\left(3 a-b-c-d+\frac{3}{2}\right)-56(a-b)-22(b-c)\right) \left(-3 a+b+c+d-\frac{3}{2}\right)-\frac{2}{39}\left(9(a-b)+7(b-c)+23(c-d)\right) \left(-a-b-c+3 d-\frac{3}{2}\right)-\frac{2}{13}(-a-b+c+d-1) \left(7(-a-b+c+d-1)+22(b-c)+4(c-d)\right)$$ Each term is $\le0$, so the minimum of $\alpha$ is $\frac54$, equality obtained when $a=0, b=\frac{1}{4}, c=\frac{1}{2}, d=\frac{3}{4}$.

Is the above proof correct? How to deal with other values of $n$?