Let the integer $n \ge 2$ , and $x_1,x_2,\cdots,x_n $ be real numbers such that $\sum_{k=1}^nx_k$ be integer . $d_k=\underset{m\in {Z}}{\min}\left|x_k-m\right| $, $1\leq k\leq n$ .Find the maximum value of $\sum_{k=1}^nd_k$.
Problem
Source: China Yinchuan Aug 16, 2015
Tags: inequalities, algebra
17.08.2015 14:18
The answer is $\left[\frac{n}{2}\right]$. Let $\{x_i\}=\frac{1}{2}\pm\epsilon_i,0\le\epsilon_i\le\frac{1}{2}$.Note that $d_k=\frac{1}{2}-\epsilon_i$.Thus $d_k\le\frac{1}{2}$.From here we split the problem in to two cases: Case $1$:$n\equiv 0\pmod{2}$ Since $d_k\le\frac{1}{2}$ it follows that $\sum_{k=1}^nd_k\le\frac{n}{2}$.The maximum of $\sum_{k=1}^nd_k$ is indeed $\frac{n}{2}$,with equality if and only if $\{x_1\}=\{x_2\}=...=\{x_n\}=\frac{1}{2}$. Note:If $\{x_1\}=\{x_2\}=...=\{x_n\}=\frac{1}{2}$,then $\sum_{k=1}^nx_k\in\mathbb{Z}$,because $\frac{n}{2}\in\mathbb{N}$. Case $2$:$n\equiv 1\pmod{2}$ Suppose that form the set $\{\{x_1\},\{x_2\},...,\{x_n\}\}$ there are exactly $k$ elements smaller that $\frac{1}{2}$.Suppose that $\{x_1\},\{x_2\},...,\{x_k\}<\frac{1}{2}$.Then the sum $\sum_{k=1}^nx_k$ is equal to $\frac{n}{2}+\sum_{i=k+1}^{n}\epsilon_{i} -\sum_{i=1}^{k}\epsilon_{i}$.Note that $\frac{n-1}{2}\in\mathbb{N}$,so the number $\frac{1}{2}+\sum_{i=k+1}^{n}\epsilon_{i} -\sum_{i=1}^{k}\epsilon_{i}$ must be an integer(because $\sum_{k=1}^nx_k$ is an integer). Therefore $\sum_{i=k+1}^{n}\epsilon_{i} -\sum_{i=1}^{k}\epsilon_{i}=S+\frac{1}{2}$,for some integer $S$.This forces that $\left|\sum_{i=k+1}^{n}\epsilon_{i} -\sum_{i=1}^{k}\epsilon_{i}\right|\ge\frac{1}{2}$,resulting that $\sum_{i=1}^{n}\epsilon_i\ge\frac{1}{2}$. Finally,we have $\sum_{k=1}^nd_k=\frac{n}{2}-(\epsilon_1+\epsilon_2+...+\epsilon_{n})\le\frac{n}{2}-\frac{1}{2}=\frac{n-1}{2}$.The maximum of $\sum_{k=1}^nd_k$ is indeed $\frac{n-1}{2}$.An example for which $\sum_{k=1}^nd_k=\frac{n-1}{2}$ is when $x_1=x_2=...=x_{n-1}=\frac{1}{2}$ and $x_n=0$.(Note that if $x_1=x_2=...=x_{n-1}=\frac{1}{2}$ and $x_n=0$,then $\sum_{k=1}^nx_k\in\mathbb{Z}$,because $\frac{n-1}{2}\in\mathbb{N}$.) Now from the above two cases we can conclude that the maximum value of $\sum_{k=1}^nd_k$ is $\left[\frac{n}{2}\right]$.
27.03.2016 10:52
WLOG let all $x_i\in [0,1)$.Note that $d_k= \left| \left\lfloor x_k +\frac{1}{2}\right\rfloor-x_k\right|$. WLOG let $x_1,\ldots ,x_k\in \left[0,\frac{1}{2}\right), x_{k+1},\ldots , x_n\in \left[\frac{1}{2}, 1\right)$. For $1\le i\le k$, $d_i=x_i,$ for $k+1\le i\le n$, $d_i=1-x_i$. Thus note \begin{align*} \sum d_i & = x_1+\ldots + x_k + (1-x_{k+1})+\ldots + (1-x_n)\\ &= n-k+x_1+\ldots + x_k - x_{k+1}-\ldots - x_n\\ &= \sum x_i + n-k -2(x_{k+1}+\ldots + x_n)\\ &\le \sum x_i \end{align*}where the last inequality is due to $x_i\ge \frac{1}{2}$ for $k+1\le i\le n$. On the other hand \begin{align*} n-k+x_1+\ldots + x_k - x_{k+1}-\ldots - x_n & = n-k-\sum x_i +2(x_1+\ldots +x_k)\\ &\le n-\sum x_i \end{align*}where the last inequality is due to $x_i\le \frac{1}{2}$ for $1\le i\le k$. Thus follows that $\sum d_i\le \min(\sum x_i, n-\sum x_i)\implies \sum d_i\le \left\lfloor \frac{n}{2}\right\rfloor$ since $\sum x_i$ is an integer, and the construction for $\sum d_i=\left\lfloor \frac{n}{2}\right\rfloor$ can be seen above.
17.08.2017 13:46
We will show that the answer is $\lfloor \frac{n}{2} \rfloor$. Here's an example showing that $\lfloor \frac{n}{2} \rfloor$ is possible. For $n$ even: $x_1= x_2 = \cdots = x_n= \frac{1}{2}$ For $n$ odd: $x_1 = x_2 = \cdots = x_n = \frac{n+1}{2n}$. It is easy to see that these two are indeed sufficient examples. Now we will show that this is indeed the maximum. If $n$ is even, from the trivial fact $d_k \le \frac{1}{2}$, we get $\sum_{k=1}^n d_k \le \frac{n}{2}$. If $n$ is odd, we will first replace $x_i$ with $x_i - \lfloor x_i \rfloor$, which is a valid transformation for obvious reasons. Then notice $d_k = \text{min}(x_i, 1-x_i) = \frac{1}{2} ( 1- |2x_i-1|)$. This enables us to write $$ \sum_{k=1}^n d_k = \frac{n}{2} - \frac{1}{2} \sum_{k=1}^n |2x_k - 1| $$Meanwhile, $\sum_{k=1}^n (2x_k-1)$ is an odd integer. This shows that, by the triangle inequality, $$\sum_{k=1}^n d_k = \frac{n}{2} - \frac{1}{2} \sum_{k=1}^n \left| 2x_k - 1 \right| \le \frac{n}{2} - \frac{1}{2} \left| \sum_{k=1}^n (2x_k -1) \right| \le \frac{n-1}{2}$$
09.08.2019 18:55
Sorry but can you explain for me why $d_k = \min_{m \in \mathbb{Z}} \left|x_k - m \right| \le \frac{1}{2} \ ?$
09.08.2019 20:03
Do you need a rigorous proof or is it enough to see that distance between real number and the nearest integer is at most half?