Западно-Китайская математическая олимпиада, 2015 год

Дано натуральное число $n \ge 2$, и $x_1,x_2,\ldots,x_n$ действительные числа такие, что сумма $\sum_{k=1}^nx_k$ — целое число. Пусть $d_k=\underset{m\in {Z}}{\min}\left|x_k-m\right|$, $1\leq k\leq n$. Найдите максимум суммы $\sum_{k=1}^nd_k$.

Комментарий/решение

Ответ: $[\dfrac n 2]$

Пусть $x_i-[x_i]=y_i\in [0;1),$ для $i=1,\ldots,n.$ Следовательно $y_1+\ldots+y_n=y\in\mathbb Z.$ Заменим $D=\sum\limits_{k = 1}^n {{d_k}}.$

Легко понять, что $d_k=\underset{m\in {Z}}{\min}\left|x_k-m\right|=\min \{y_k,1-y_k \},$ для $k=1,\ldots,n.$

$\\$

БОО примем, что $y_1,\ldots,y_s\le\dfrac 1 2$ и $y_{s+1},\ldots,y_n\ge\dfrac 1 2\implies d_i=y_i,\forall 1\le i\le s$ и $d_i=1-y_i,\forall s+1\le i\le n.$

Тогда $$(\mathrm i)\quad D=y_1+\ldots+y_s+(1-y_{s+1})+\ldots+(1-y_n)=y+(n-s)-2(y_{s+1}+\ldots+y_n)\le y+(n-s)-2(\dfrac{n-s}{2})=y,$$

$$(\mathrm{ii})\quad D=y_1+\ldots+y_s+(1-y_{s+1})+\ldots+(1-y_n)=2(y_1+\ldots+y_s)+(n-s)-y\le 2(\dfrac{s}{2})+(n-s)-y=n-y,$$

в следствии $D\le \min\{y,n-y\}\le [\dfrac n 2],$ так как $y\in\mathbb Z.$

Пример:

Для четных $n$: $x_1 = x_2 = \cdots = x_n = \dfrac {1} {2}$

Для нечетных $n$: $x_1 = x_2 = \cdots = x_{n-1} = \dfrac 1 2, x_n=0$